Binary Tree Upside Down
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
0and10nodes. 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Brute force (store the left edge) | O(h) | O(h) |
| Recursive | O(h) | O(h) |
| Optimal (iterative pointer rewiring) | O(h) | O(1) |
1Brute force (store the left edge)
O(h)Only the nodes on the left edge are touched, each a constant number of times.O(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.
- If root is null return null. Walk root, root.left, ... and store each node in spine.
- For i from the last index down to 1: spine[i].left = spine[i - 1].right; spine[i].right = spine[i - 1].
- 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);
}
}class Solution:
def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
spine = []
n = root
while n:
spine.append(n)
n = n.left
for i in range(len(spine) - 1, 0, -1):
node, parent = spine[i], spine[i - 1]
node.left = parent.right
node.right = parent
root.left = None
root.right = None
return spine[-1]class Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root) {
if (root == nullptr) return nullptr;
vector<TreeNode*> spine;
for (TreeNode* n = root; n != nullptr; n = n->left) spine.push_back(n);
for (int i = spine.size() - 1; i >= 1; i--) {
spine[i]->left = spine[i - 1]->right;
spine[i]->right = spine[i - 1];
}
root->left = nullptr;
root->right = nullptr;
return spine.back();
}
};function upsideDownBinaryTree(root) {
if (root === null) return null;
const spine = [];
for (let n = root; n !== null; n = n.left) spine.push(n);
for (let i = spine.length - 1; i >= 1; i--) {
spine[i].left = spine[i - 1].right;
spine[i].right = spine[i - 1];
}
root.left = null;
root.right = null;
return spine[spine.length - 1];
}2Recursive
O(h)One call per node on the left edge.O(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.
- If root is null or root.left is null, return root.
- newRoot = upsideDown(root.left).
- root.left.left = root.right; root.left.right = root.
- 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;
}
}class Solution:
def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None or root.left is None:
return root
new_root = self.upsideDownBinaryTree(root.left)
root.left.left = root.right
root.left.right = root
root.left = None
root.right = None
return new_rootclass Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root) {
if (root == nullptr || root->left == nullptr) return root;
TreeNode* newRoot = upsideDownBinaryTree(root->left);
root->left->left = root->right;
root->left->right = root;
root->left = nullptr;
root->right = nullptr;
return newRoot;
}
};function upsideDownBinaryTree(root) {
if (root === null || root.left === null) return root;
const 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)
O(h)Each node of the left edge is visited once.O(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.
- cur = root, prev = null, prevRight = null.
- While cur is not null: next = cur.left; cur.left = prevRight; prevRight = cur.right; cur.right = prev; prev = cur; cur = next.
- 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;
}
}class Solution:
def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
cur, prev, prev_right = root, None, None
while cur:
nxt = cur.left
cur.left = prev_right
prev_right = cur.right
cur.right = prev
prev = cur
cur = nxt
return prevclass Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root) {
TreeNode *cur = root, *prev = nullptr, *prevRight = nullptr;
while (cur != nullptr) {
TreeNode* next = cur->left;
cur->left = prevRight;
prevRight = cur->right;
cur->right = prev;
prev = cur;
cur = next;
}
return prev;
}
};function upsideDownBinaryTree(root) {
let cur = root, prev = null, prevRight = null;
while (cur !== null) {
const 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.