How to Solve Binary Tree Upside Down

Written By
Adam Bhula

Binary Tree Upside Down Introduction

The Binary Tree Upside Down problem asks us to flip a given binary tree where every right node is a leaf into one where left nodes are leaves. This problem requires us to carefully iterate through the tree and perform a transformation at each node, keeping in mind to update our pointers along the way.

Binary Tree Upside Down Problem

Given a binary tree where every node has either 0 or 2 children and every right node is a leaf node, flip it upside down turning it into a binary tree where all left nodes are leaf nodes.

Example Input and Output


Input: {1,2,3,4,5} Output: {4,5,2,#,#,3,1} Explanation: The input is 1 /
2 3 /
4 5 and the output is 4 /
5 2 /
3 1

Binary Tree Upside Down Solutions

To solve this problem, we can use an iterative approach to flip the binary tree upside down. We can start by initializing three pointers: prev, curr, and next. We iterate through the tree, updating the pointers and performing the transformation at each node.

During the iteration, we update the next pointer to the left child of the current node, as it will become the next node to process. We can then perform the transformation by assigning the left child of the current node to a temporary variable, and the right child to the prev pointer. We update prev to the current node and curr to the next node, and repeat this process until we reach a leaf node.

By flipping the child pointers and updating the temporary variable and pointers, we gradually transform the binary tree to its upside-down form. Finally, we return the prev pointer, which will be the new root of the upside-down tree.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def upside_down_binary_tree(root):
    if not root:
        return None

    prev = None
    curr = root
    next = None
    temp = None

    while curr:
        next = curr.left
        curr.left = temp
        temp = curr.right
        curr.right = prev
        prev = curr
        curr = next

    return prev

#functions to help us test our solution
def construct_tree():
    # Create the binary tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    return root

#functions to help us test our solution
def print_tree(root):
    if not root:


# Driver code
root = construct_tree()
print("Original Tree:")

upside_down_root = upside_down_binary_tree(root)
print("\nUpside Down Tree:")

Time/Space Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes in the tree. This is because we need to visit each node once to perform the transformation.
  • Space Complexity: O(1), as we use a constant amount of extra space.

About is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.