We start by setting the global pointer 'prev' to null before any recursion begins. This pointer will track the previously processed node in the flattened list.
💡 This initialization is crucial because 'prev' holds the last processed node, allowing us to link the current node's right pointer correctly.
Line:prev = None
💡 Understanding that 'prev' starts as null sets the base case for linking nodes from the bottom up.
traverse
Start recursion at root node 1
The recursion begins at the root node with value 1. The node state changes to active as we start processing it.
💡 Starting at the root is the natural entry point for the recursive flattening process.
Line:def flatten(root: Optional[TreeNode]) -> None:
if not root:
return
flatten(root.right) # STEP 2
💡 The algorithm will first recurse into the right subtree before the left, following the reverse preorder traversal.
traverse
Recurse into right child node 5
From node 1, the recursion moves to its right child node 5, marking it active for processing.
💡 Following the right subtree first ensures the linked list is built from the rightmost node backwards.
Line:flatten(root.right) # STEP 3
💡 The traversal order is right subtree first, which is key to correctly rewiring pointers.
traverse
Recurse into right child node 6
From node 5, the recursion moves to its right child node 6, marking it active for processing.
💡 Continuing right-first traversal reaches the rightmost leaf node, which will be the tail of the flattened list.
Line:flatten(root.right) # STEP 4
💡 The rightmost node is processed first, setting the base for linking nodes backward.
insert
Process node 6: set right to prev (null), left to null, update prev
At node 6, set node.right to prev (currently null), node.left to null, then update prev to node 6.
💡 This step rewires node 6 as the tail of the linked list, starting the chain.
💡 Node 1 now points to node 3, completing the flattened linked list starting at the root.
reconstruct
Traversal complete: flattened linked list formed
The recursion has finished. The tree is now flattened into a linked list starting at node 1, with all left pointers null and right pointers following preorder.
💡 This final step confirms the algorithm's success in transforming the tree structure.
Line:flatten(root) # recursion complete
💡 The flattened list is 1 -> 2 -> 3 -> 4 -> 5 -> 6, matching preorder traversal.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
prev = None # STEP 1
def flatten(root: Optional[TreeNode]) -> None:
global prev
if not root:
return
flatten(root.right) # STEP 2-4
flatten(root.left) # STEP 6,8,9,11
root.right = prev # STEP 5,7,10,12,13
root.left = None # STEP 5,7,10,12,13
prev = root # STEP 5,7,10,12,13
# Driver code
if __name__ == '__main__':
root = TreeNode(1,
TreeNode(2, TreeNode(3), TreeNode(4)),
TreeNode(5, None, TreeNode(6)))
flatten(root) # STEP 14
curr = root
while curr:
print(curr.val, end=' -> ' if curr.right else '')
curr = curr.right
print()
📊
Flatten Binary Tree to Linked List - Watch the Algorithm Execute, Step by Step
Watching this step-by-step visualization reveals how the reverse preorder traversal and pointer rewiring work together to flatten the tree efficiently, which is difficult to grasp from code alone.
Step 1/14
·Active fill★Answer cell
123456
Current node: 1
123456
DFS Stack
1 (entered)
Current node: 5
123456
DFS Stack
5 (entered)1 (right_done)
Current node: 6
123456
DFS Stack
6 (entered)5 (right_done)1 (right_done)
Current node: 6
123456
DFS Stack
5 (right_done)1 (right_done)
123456
DFS Stack
5 (left_done)1 (right_done)
Current node: 5
123456
DFS Stack
1 (right_done)
Current node: 2
123456
DFS Stack
2 (entered)1 (left_done)
Current node: 4
123456
DFS Stack
2 (right_done)1 (left_done)
Current node: 4
123456
DFS Stack
2 (right_done)1 (left_done)
Current node: 3
123456
DFS Stack
3 (entered)2 (left_done)1 (left_done)
Current node: 3
123456
DFS Stack
1 (left_done)
Current node: 1
123456
123456
Result: [1, 2, 3, 4, 5, 6]
Key Takeaways
✓ The reverse preorder traversal (right-left-root) is essential to flatten the tree from the bottom up.
This traversal order is counterintuitive but necessary to link nodes correctly without losing references.
✓ The global 'prev' pointer tracks the last processed node, enabling each node to link to the next node in the flattened list.
Understanding 'prev' is key to grasping how the linked list is constructed incrementally.
✓ Setting each node's left pointer to null and right pointer to 'prev' rewires the tree into a singly linked list in-place.
This pointer manipulation is the core transformation that converts the tree structure.
Practice
(1/5)
1. Given the following code snippet for building a tree from inorder and postorder traversals, what is the value of inorder_index after processing the first iteration of the for-loop when inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]?
easy
A. 4
B. 2
C. 1
D. 3
Solution
Step 1: Initialize variables
inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).
Step 2: First iteration (i=3, node_val=20)
top.val=3 != inorder[4]=7, so attach 20 as right child, stack grows, inorder_index stays 4.
Step 3: Second iteration (i=2, node_val=7)
top.val=20 != inorder[4]=7 is false, so enter else: pop stack while top.val == inorder[inorder_index]. 20 != 7, so no pop, attach 7 as right child, stack grows, inorder_index stays 4.
Step 4: Third iteration (i=1, node_val=15)
top.val=7 == inorder[4]=7, pop 7, inorder_index=3; top.val=20 == inorder[3]=20, pop 20, inorder_index=2; top.val=3 != inorder[2]=15, stop popping. Attach 15 as left child, stack grows.
Final Answer:
Option D -> Option D
Quick Check:
inorder_index decremented twice after popping 7 and 20 [OK]
Hint: inorder_index decrements only when popping matching nodes [OK]
Common Mistakes:
Off-by-one error in inorder_index update
Confusing when to pop stack
Misreading top.val vs inorder[inorder_index]
2. Consider the following iterative DFS code for finding all root-to-leaf paths with a given sum. Given the tree below and targetSum = 7, what is the final returned list?
Tree structure:
5
/ \
4 8
/ / \
11 13 4
Target sum: 7
def pathSum(root, targetSum):
if not root:
return []
res = []
stack = [(root, [root.val], root.val)]
while stack:
node, path, current_sum = stack.pop()
if not node.left and not node.right:
if current_sum == targetSum:
res.append(path)
if node.right:
stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
if node.left:
stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
return res
Since no leaf path sums to 7, result list remains empty.
Final Answer:
Option A -> Option A
Quick Check:
No leaf path sums to 7, so empty list returned [OK]
Hint: Check sums only at leaf nodes [OK]
Common Mistakes:
Confusing intermediate node sums with leaf sums
Forgetting to check leaf condition
3. The following code attempts to count nodes in a complete binary tree using the optimal approach. Identify the line containing the subtle bug that can cause incorrect counts for incomplete last levels.
def exists(idx, h, root):
left, right = 0, 2**(h - 1) - 1
for _ in range(h - 1):
mid = (left + right) // 2
if idx < mid: # Bug here
root = root.left
right = mid
else:
root = root.right
left = mid + 1
return root is not null
medium
A. Line with 'if idx < mid:'
B. Line with 'return root is not null'
C. Line with 'root = root.right'
D. Line with 'left, right = 0, 2**(h - 1) - 1'
Solution
Step 1: Understand binary search condition
The condition should be 'if idx <= mid' to correctly include mid index in left subtree.
Step 2: Identify impact of bug
Using 'idx < mid' excludes mid index from left subtree, causing incorrect traversal and wrong node existence checks.
Final Answer:
Option A -> Option A
Quick Check:
Correct binary search must include mid index [OK]
Hint: Binary search must use <= to include mid index [OK]
Common Mistakes:
Using < instead of <= in binary search condition
4. Examine the following buggy iterative DFS code for finding all root-to-leaf paths with a given sum. Which line contains the subtle bug that causes incorrect results?
def pathSum(root, targetSum):
if not root:
return []
res = []
stack = [(root, [root.val], root.val)]
while stack:
node, path, current_sum = stack.pop()
if current_sum == targetSum:
res.append(path)
if node.right:
stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
if node.left:
stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
return res
medium
A. Line appending left child to stack
B. Line initializing stack with root node and path
C. Line appending right child to stack
D. Line checking if current_sum == targetSum without verifying leaf node
Solution
Step 1: Identify condition for adding path to results
Correct code adds path only if current node is leaf and sum matches.
Step 2: Locate bug
Here, path is added whenever sum matches, regardless of leaf status, causing incomplete paths to be included.
Final Answer:
Option D -> Option D
Quick Check:
Missing leaf check causes incorrect paths in results [OK]
Hint: Always check leaf node before adding path [OK]
Common Mistakes:
Adding path before confirming leaf node
Forgetting to backtrack in recursion
5. Consider the following buggy deserialization code snippet for BFS-based tree reconstruction. Which line contains the subtle bug that causes incorrect tree structure when deserializing?
def deserialize(data):
if not data:
return None
vals = data.split(',')
root = TreeNode(int(vals[0]))
queue = deque([root])
i = 1
while queue:
node = queue.popleft()
if vals[i] != 'X':
node.left = TreeNode(int(vals[i]))
queue.append(node.left)
i += 1
if vals[i] != 'X':
node.right = TreeNode(int(vals[i]))
queue.append(node.right)
i += 1
return root
medium
A. Line: if vals[i] != 'X': (left child check)
B. Line: i += 1 (after left child assignment)
C. Line: if vals[i] != 'X': (right child check)
D. Line: while queue: (loop condition)
Solution
Step 1: Identify potential infinite loop
The loop condition 'while queue:' does not check if 'i' has exceeded vals length, risking index out of range or infinite loop.
Step 2: Understand impact on deserialization
Without checking 'i < len(vals)', the loop may continue after all nodes processed, causing errors or incorrect tree structure.
Final Answer:
Option D -> Option D
Quick Check:
Loop condition must ensure 'i' stays within bounds to avoid deserialization bugs [OK]
Hint: Loop must check index bounds to avoid infinite loops [OK]
Common Mistakes:
Not checking index bounds in deserialization loops
Mixing up left and right child assignments
Forgetting to append children to queue
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.