Binary Tree Upside Down

Medium Trees & BST Recursion Original on LeetCode

Reported atLinkedIn

Binary Tree Upside Down is a medium trees & bst problem solved with the recursion pattern. The best approach, optimal (iterative pointer rewiring), runs in O(h) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (store the left edge) up.

Problem

You are given the root of a binary tree with a special shape: every right child has a left sibling (it shares a parent with a left child) and has no children of its own. Only the nodes on the leftmost path can have children.

Turn the tree upside down and return the new root. Level by level, starting from the bottom of the left edge:

  • the original left child becomes the new root of that part,
  • the original right child (its sibling) becomes the new root’s left child,
  • the original parent becomes the new root’s right child.

Examples

Example 1

Input
root = [3,6,2,9,5]
Output
[9,5,6,null,null,2,3]
Why
9, the deepest node on the left edge, becomes the root. Its old sibling 5 becomes its left child and its old parent 6 its right child, and the same step repeats one level up with 2 and 3.

Example 2

Input
root = [7,8,9]
Output
[8,9,7]
Why
8 becomes the root, its sibling 9 moves to the left and the old root 7 moves to the right.

Example 3

Input
root = []
Output
[]
Why
An empty tree stays empty.

Constraints

  • The tree has between 0 and 10 nodes.
  • 1 <= Node.val <= 10
  • Every right child has a left sibling and no children of its own.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (store the left edge)O(h)O(h)
RecursiveO(h)O(h)
Optimal (iterative pointer rewiring)O(h)O(1)

1Brute force (store the left edge)

TimeO(h)Only the nodes on the left edge are touched, each a constant number of times.
SpaceO(h)The list stores the h nodes of the left edge.

Put every node of the leftmost path into a list. Then, from the bottom of the list upward, give each node its parent's old right child as the left child and its parent as the right child. Finally cut the old root's children so it becomes a leaf.

  1. If root is null return null. Walk root, root.left, ... and store each node in spine.
  2. For i from the last index down to 1: spine[i].left = spine[i - 1].right; spine[i].right = spine[i - 1].
  3. Set spine[0].left = spine[0].right = null and return the last node of spine.
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null) return null;
        List<TreeNode> spine = new ArrayList<>();
        for (TreeNode n = root; n != null; n = n.left) spine.add(n);
        for (int i = spine.size() - 1; i >= 1; i--) {
            TreeNode node = spine.get(i), parent = spine.get(i - 1);
            node.left = parent.right;
            node.right = parent;
        }
        root.left = null;
        root.right = null;
        return spine.get(spine.size() - 1);
    }
}

2Recursive

TimeO(h)One call per node on the left edge.
SpaceO(h)The recursion stack is as deep as the left edge.

Flip the left subtree first; its result is the final root. After that call, root.left is still the old left child, which is now the bottom-right node of the flipped part, so attach root.right as its left child and root as its right child, then clear root's own pointers.

  1. If root is null or root.left is null, return root.
  2. newRoot = upsideDown(root.left).
  3. root.left.left = root.right; root.left.right = root.
  4. root.left = root.right = null; return newRoot.
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null || root.left == null) return root;
        TreeNode newRoot = upsideDownBinaryTree(root.left);
        root.left.left = root.right;
        root.left.right = root;
        root.left = null;
        root.right = null;
        return newRoot;
    }
}

3Optimal (iterative pointer rewiring)

TimeO(h)Each node of the left edge is visited once.
SpaceO(1)Only four pointers, no stack or recursion.

Walk down the left edge like reversing a linked list. Keep prev (the node just processed, which becomes the current node's right child) and prevRight (the old right child of prev, which becomes the current node's left child). Save cur.left and cur.right before overwriting them.

  1. cur = root, prev = null, prevRight = null.
  2. While cur is not null: next = cur.left; cur.left = prevRight; prevRight = cur.right; cur.right = prev; prev = cur; cur = next.
  3. Return prev.
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode cur = root, prev = null, prevRight = null;
        while (cur != null) {
            TreeNode next = cur.left;
            cur.left = prevRight;
            prevRight = cur.right;
            cur.right = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

Edge cases to test

  • Empty tree
  • A single node
  • Only left children (a left chain with no right children at all)
  • Some levels of the left edge have a right sibling and others do not

Hints

Hint 1

Only nodes on the leftmost path ever have children. The deepest node of that path becomes the new root.

Hint 2

Walking back up the left edge, every node gets its parent's right child as its new left child, and its parent as its new right child.

Hint 3

This is like reversing a linked list along the left edge: you can do it top-down with a few pointers and no stack, as long as you remember the previous node and its old right child.

FAQ

What is the best time complexity for Binary Tree Upside Down?

Optimal (iterative pointer rewiring) runs in O(h) time and O(1) extra space. Each node of the left edge is visited once.

Which pattern does Binary Tree Upside Down use?

It is a trees & bst problem that uses the recursion pattern. Other problems with the same pattern: Binary Tree Inorder Traversal (Recursive), Binary Tree Preorder Traversal (Recursive), Binary Tree Postorder Traversal (Recursive).

Is there a brute force solution for Binary Tree Upside Down?

Yes. Brute force (store the left edge) takes O(h) time and O(h) space. Put every node of the leftmost path into a list.

Which edge cases should I test for Binary Tree Upside Down?

Empty tree; A single node; Only left children (a left chain with no right children at all); Some levels of the left edge have a right sibling and others do not.