MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Binary Tree Upside Down

Written By

## 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

#### Example

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:
return

print(root.val)
print_tree(root.left)
print_tree(root.right)

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

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

#### 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.