Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Binary Tree Upside Down solution and explanation

MediumBinary TreeDepth-First SearchTree4 min read65.4% acceptanceUpdated 23 Mar 2026Premium elsewhere, free here
Asked atLinkedInGoogle
Practise Binary Tree Upside Down
13:18
LeetCode 156. Binary Tree Upside DownHappy Coding · 13:18 · 6K viewsWatch on YouTube
9 more videos on this problem
  1. LeetCode 156. Binary Tree Upside DownHappy Coding · 13:18 · 6K views
  2. 米开 LeetCode 156. Binary Tree Upside DownM.C米开朗基罗 · 2:47 · 1K views
  3. Leetcode 156(medium). Binary Tree Upside Down【Recursion/Tree】中文AndroidBabies安卓大宝贝们 · 11:36 · 1K views
  4. Binary Tree Upside Down - 156 Leetcode Premium - Python - Easy solutionLeet Programmer · 8:39 · 1K views
  5. Binary Tree Upside Down - Leetcode 156 - Multiple solutions explained (Kotlin)Vahid Hoss · 18:54 · 802 views
  6. Interview, Swift, Tree, leetcode, 156. Binary Tree Upside Down with Recursive solution (LinkedIn)Soonin Coding Challenge · 11:06 · 195 views
  7. 156. Binary Tree Upside Down (LeetCode, Java)hakunamatasq · 3:12 · 190 views
  8. Leetcode 156. Binary Tree Upside Down in Python | Python Leetcode | Python Coding Tutorial | ASMRCode is Art · 2:14 · 152 views
  9. Leetcode 156. Binary Tree Upside DownIH Zonaid · 13:31 · 105 views
  10. Interview, Swift, Tree, leetcode, 156. Binary Tree Upside Down with Iterative solution (LinkedIn)Soonin Coding Challenge · 15:39 · 81 views

The problem

Given the root of a binary tree, turn the tree upside down and return the new root.

You can turn a binary tree upside down with the following steps:

  1. The original left child becomes the new root.
  2. The original root becomes the new right child.
  3. The original right child becomes the new left child.

The mentioned steps are done level by level. It is guaranteed that every right node has a sibling (a left node with the same parent) and has no children.

Example 1:

Input: root = [1,2,3,4,5]
Output: [4,5,2,null,null,3,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

  • The number of nodes in the tree will be in the range [0, 10].
  • 1 <= Node.val <= 10
  • Every right node in the tree has a sibling (a left node that shares the same parent).
  • Every right node in the tree has no children.

Approach overview

Problem Overview: You are given a binary tree where every right child is either null or a leaf with a sibling. The task is to flip the tree upside down so the leftmost node becomes the new root. During the transformation, the original parent becomes the right child and the original right sibling becomes the left child.

Approach 1: Recursive DFS Re-linking (O(n) time, O(h) space)

This method uses recursion to reach the leftmost node, which will become the new root of the flipped tree. Starting from the root, recursively process root.left until the base case (a node with no left child). While the recursion unwinds, rewire pointers: the original left child's left pointer becomes the original right child, and its right pointer becomes the original parent. After rewiring, clear the original node’s left and right references to avoid cycles. The algorithm visits each node exactly once, giving O(n) time complexity. The recursion stack uses O(h) space where h is the height of the tree. This approach fits naturally with Depth-First Search patterns and is often the clearest way to reason about pointer transformations in a Binary Tree.

Approach 2: Iterative Pointer Reversal (O(n) time, O(1) space)

The iterative version performs the same transformation but avoids recursion by tracking previous nodes. Traverse down the left spine of the tree using a loop. Maintain three references: the current node, the previous parent, and the previous right child. At each step, store the next left node, then rotate pointers so the current node’s left becomes the previous right child and its right becomes the previous parent. Update the tracking pointers and continue moving left. This effectively reverses the structure layer by layer until the traversal reaches the leftmost node, which becomes the new root. Because the algorithm only stores a few pointers, it runs in O(n) time with O(1) extra space. This technique resembles linked list reversal applied along the left spine of a Tree.

Recommended for interviews: The recursive DFS solution is usually the expected explanation because it clearly expresses the structural transformation and demonstrates comfort with recursion on trees. The iterative pointer-reversal variant shows deeper understanding of pointer manipulation and space optimization. Start with the recursive explanation to demonstrate correctness, then mention the iterative O(1) space improvement if time allows.

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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.right = root
        root.left.left = root.right
        root.left = None
        root.right = None
        return new_root
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null || root.left == null) {
            return root;
        }
        TreeNode newRoot = upsideDownBinaryTree(root.left);
        root.left.right = root;
        root.left.left = root.right;
        root.left = null;
        root.right = null;
        return newRoot;
    }
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        if (!root || !root->left) return root;
        TreeNode* newRoot = upsideDownBinaryTree(root->left);
        root->left->right = root;
        root->left->left = root->right;
        root->left = nullptr;
        root->right = nullptr;
        return newRoot;
    }
};
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func upsideDownBinaryTree(root *TreeNode) *TreeNode {
	if root == nil || root.Left == nil {
		return root
	}
	newRoot := upsideDownBinaryTree(root.Left)
	root.Left.Right = root
	root.Left.Left = root.Right
	root.Left = nil
	root.Right = nil
	return newRoot
}
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Recursive DFS Re-linkingO(n)O(h)Best for clarity and typical interview explanations using recursion
Iterative Pointer ReversalO(n)O(1)When minimizing extra memory or demonstrating advanced pointer manipulation

Frequently asked questions

Is Binary Tree Upside Down easy or hard?

Binary Tree Upside Down is considered a medium-level problem. The traversal itself is straightforward, but correctly reassigning pointers without breaking the tree requires careful reasoning about parent, left child, and right sibling relationships.

Binary Tree Upside Down Python/Java solution

Both Python and Java implementations typically use a recursive DFS helper that returns the new root after reaching the leftmost node. During recursion unwinding, the code reassigns child pointers to flip the structure. The same logic translates directly to C++ and Go with O(n) time complexity.

How to solve Binary Tree Upside Down in O(n)?

Traverse down the left side of the tree using recursion or iteration. When processing a node, redirect the original left child's left pointer to the original right child and its right pointer to the original parent. Each node is processed once, producing an O(n) time solution.

What is the best approach for Binary Tree Upside Down?

The recursive DFS pointer re-linking approach is the most common solution. Traverse to the leftmost node and reassign pointers while the recursion unwinds so each node’s left child becomes the new parent. This runs in O(n) time and O(h) space, where h is the tree height. Many interviewers expect this explanation because it clearly demonstrates tree recursion.

Is Binary Tree Upside Down asked at Google/Amazon/Meta?

Binary tree transformation and pointer manipulation problems appear in interviews at companies like Google, Amazon, and Meta. Variations of tree restructuring and DFS-based pointer updates are commonly used to evaluate understanding of tree traversal and recursion.

What data structure is used in Binary Tree Upside Down?

The problem operates directly on a binary tree structure. Solutions rely on Depth-First Search traversal and pointer manipulation to restructure parent-child relationships while maintaining tree integrity.

What is the time complexity of Binary Tree Upside Down?

Binary Tree Upside Down runs in O(n) time because each node is visited exactly once during the transformation. The recursive solution uses O(h) auxiliary space from the call stack, where h is the tree height. An iterative version reduces extra space to O(1).

Comments

Next problem · similarReverse Linked ListEasy
Now write it yourselfClose this page and solve Binary Tree Upside Down in the editor, without looking.
Practise Binary Tree Upside Down