Binary Tree Upside Down

Question

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:

Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1

Solution

At each node you want to assign: p.left = parent.right; p.right = parent;

Top down approach

We need to be very careful when reassigning current node’s left and right children. Besides making a copy of the parent node, you would also need to make a copy of the parent’s right child too. The reason is the current node becomes the parent node in the next iteration.

here recursion

public TreeNode UpsideDownBinaryTree(TreeNode root) {
  if (root == null)
    return null;
  TreeNode parent = root, left = root.left, right = root.right;
  if (left != null) {
    TreeNode ret = UpsideDownBinaryTree(left);
    left.left = right;
    left.right = parent;
    return ret;
  }
  return root;
}

iteration


    public TreeNode UpsideDownBinaryTree(TreeNode root) {
        TreeNode node = root, parent = null, right = null;
        while (node != null) {
            TreeNode left = node.left;
            node.left = right;
            right = node.right;
            node.right = parent;
            parent = node;
            node = left;
        }
        return parent;
    }

postorder Traversal

private TreeNode out = null;
public TreeNode UpsideDownBinaryTree(TreeNode root) {
  TreeNode dummy = new TreeNode(0);
  dummy.left = new TreeNode(0);
  out = dummy;

  postorder(root);
  return dummy.right;
}

private void postorder(TreeNode root) {
  if (root == null)
    return;

  postorder(root.left);
  postorder(root.right);

  if (out.left == null) {
    out.left = root;
    out.left.left = null;
    out.left.right = null;
  } else if (out.right == null) {
    out.right = root;
    out.right.left = null;
    out.right.right = null;
  }

  if (out.left != null && out.right != null)
    out = out.right;
}