How to Solve Binary Tree Upside Down
Binary Tree Upside Down Introduction
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
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
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)1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7
8def upside_down_binary_tree(root):
9 if not root:
10 return None
11
12 prev = None
13 curr = root
14 next = None
15 temp = None
16
17 while curr:
18 next = curr.left
19 curr.left = temp
20 temp = curr.right
21 curr.right = prev
22 prev = curr
23 curr = next
24
25 return prev
26
27#functions to help us test our solution
28def construct_tree():
29 # Create the binary tree
30 root = TreeNode(1)
31 root.left = TreeNode(2)
32 root.right = TreeNode(3)
33 root.left.left = TreeNode(4)
34 root.left.right = TreeNode(5)
35
36 return root
37
38#functions to help us test our solution
39def print_tree(root):
40 if not root:
41 return
42
43 print(root.val)
44 print_tree(root.left)
45 print_tree(root.right)
46
47
48# Driver code
49root = construct_tree()
50print("Original Tree:")
51print_tree(root)
52
53upside_down_root = upside_down_binary_tree(root)
54print("\nUpside Down Tree:")
55print_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.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io 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.
