Flatten Binary Tree to Linked List

▶

Steps

setup

Initialize global pointer 'prev' as null

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.

Line:

root.right = prev
root.left = None
prev = root  # STEP 5

💡 Node 6 becomes the last node in the flattened list with no right child.

traverse

Recurse into left child of node 5 (null)

Node 5 has no left child, so the recursion returns immediately from this branch.

💡 Handling null children correctly avoids errors and ends recursion branches properly.

Line:

flatten(root.left)  # STEP 6

💡 Null children are base cases that stop recursion on that path.

insert

Process node 5: set right to prev (node 6), left to null, update prev

At node 5, set node.right to prev (node 6), node.left to null, then update prev to node 5.

💡 This rewiring links node 5 to node 6, building the flattened list backwards.

Line:

root.right = prev
root.left = None
prev = root  # STEP 7

💡 Node 5 now points to node 6, continuing the linked list chain.

traverse

Recurse into left child node 2

Back at node 1, recursion now moves to the left child node 2, marking it active.

💡 After processing the right subtree, the algorithm processes the left subtree to complete the flattening.

Line:

flatten(root.left)  # STEP 8

💡 The left subtree is processed after the right to maintain correct order in the flattened list.

traverse

Recurse into right child node 4

From node 2, recursion moves to its right child node 4, marking it active.

💡 Right child is processed before left child to maintain reverse preorder traversal order.

Line:

flatten(root.right)  # STEP 9

💡 Processing right child first ensures correct linking order in the flattened list.

insert

Process node 4: set right to prev (node 5), left to null, update prev

At node 4, set node.right to prev (node 5), node.left to null, then update prev to node 4.

💡 This links node 4 to node 5, continuing the flattened list chain.

Line:

root.right = prev
root.left = None
prev = root  # STEP 10

💡 Node 4 now points to node 5, extending the linked list backwards.

traverse

Recurse into left child node 3

From node 2, recursion moves to its left child node 3, marking it active.

💡 Left child is processed after right child to maintain reverse preorder traversal.

Line:

flatten(root.left)  # STEP 11

💡 Processing left child last ensures nodes are linked in preorder sequence.

insert

Process node 3: set right to prev (node 4), left to null, update prev

At node 3, set node.right to prev (node 4), node.left to null, then update prev to node 3.

💡 This links node 3 to node 4, continuing the flattened list backwards.

Line:

root.right = prev
root.left = None
prev = root  # STEP 12

💡 Node 3 now points to node 4, extending the linked list chain.

insert

Process node 1: set right to prev (node 3), left to null, update prev

Back at the root node 1, set node.right to prev (node 3), node.left to null, then update prev to node 1.

💡 This final rewiring links the root to the head of the flattened list formed by its subtrees.

Line:

root.right = prev
root.left = None
prev = root  # STEP 13

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

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. Consider the following Python code implementing the Morris Preorder Traversal approach to sum root-to-leaf numbers. Given the binary tree: 1 / \ 2 3 What is the final value of the variable total returned by sumNumbers?

easy

A. 5

B. 15

C. 25

D. 26

Solution

1. Step 1: Trace path 1->2

   current_number accumulates 1 then 12; leaf node 2 adds 12 to total.

2. Step 2: Trace path 1->3

   current_number resets to 1, then accumulates 13; leaf node 3 adds 13 to total. Total = 12 + 13 = 25.

3. Step 3: Check for off-by-one or missed increments

   Integer division after visiting left subtree correctly adjusts current_number; no extra addition occurs.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Sum of 12 and 13 is 25, matching code behavior [OK]

Hint: Trace current_number updates carefully at each node [OK]

Common Mistakes:

• Off-by-one in current_number division
• Adding non-leaf nodes to total

2. Given the following code snippet for checking if a binary tree is symmetric, what is the final return value when called with the tree root = TreeNode(1, TreeNode(2), TreeNode(2))?

from typing import Optional

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

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return t1 == t2
        if t1.val != t2.val:
            return False
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

    return isMirror(root.left, root.right) if root else True

root = TreeNode(1, TreeNode(2), TreeNode(2))
print(isSymmetric(root))  # What is the output?

easy

A. false

B. Raises an exception

C. null

D. true

Solution

1. Step 1: Trace isMirror on root.left and root.right nodes with value 2

   Both nodes exist and have equal values, so recursion continues.

2. Step 2: Recursively check left.left vs right.right and left.right vs right.left (both null)

   Since both pairs are null, isMirror returns true for these calls, so overall returns true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Symmetric tree with equal child nodes returns true [OK]

Hint: Symmetric tree with equal children returns true [OK]

Common Mistakes:

• Confusing null checks causing exceptions
• Returning false prematurely on equal nodes
• Misreading recursion base cases

3. What is the time complexity of the BFS-based serialization and deserialization of a binary tree with n nodes, assuming the tree is balanced? Consider both serialization and deserialization separately.

medium

A. Serialization: O(n log n), Deserialization: O(n log n)

B. Serialization: O(n), Deserialization: O(n^2)

C. Serialization: O(n), Deserialization: O(n)

D. Serialization: O(n^2), Deserialization: O(n)

Solution

1. Step 1: Analyze serialization time

   Each node is enqueued and dequeued exactly once, so serialization is O(n).

2. Step 2: Analyze deserialization time

   Deserialization processes each node once, reconstructing the tree in O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both serialization and deserialization scale linearly with number of nodes [OK]

Hint: Each node is processed once in BFS serialization/deserialization [OK]

Common Mistakes:

• Assuming deserialization is O(n^2) due to nested loops
• Confusing tree height with number of nodes
• Thinking serialization is O(n log n) due to queue operations

4. Suppose the problem is modified so that the tree can have nodes with arbitrary large depth, and you want to avoid recursion stack overflow. Which approach is best to check if the tree is balanced efficiently?

hard

A. Use the brute force recursive height check since it is simpler to implement.

B. Use iterative postorder traversal with a stack to compute heights and check balance.

C. Use a breadth-first traversal and check balance at each level.

D. Use a global variable to store height and recurse with tail recursion optimization.

Solution

1. Step 1: Understand recursion stack limitations

   Deep trees can cause recursion stack overflow in recursive solutions.

2. Step 2: Identify iterative approach benefits

   Iterative postorder traversal uses explicit stack, avoiding recursion limits and still computes heights and balance in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Iterative approach avoids recursion depth issues [OK]

Hint: Iterative traversal avoids recursion stack overflow [OK]

Common Mistakes:

• Assuming recursion with tail call optimization works in Python
• Using BFS which does not check subtree height balance
• Choosing brute force recursion despite stack limits

5. Suppose you want to perform inorder traversal on a binary tree where nodes can have parent pointers but no left or right child pointers. Which approach correctly produces the inorder sequence without recursion or extra stack?

hard

A. Use Morris traversal by creating threads on parent pointers instead of child pointers.

B. Use breadth-first search since parent pointers allow level order traversal.

C. Use recursive traversal ignoring parent pointers, which will fail due to missing child links.

D. Use iterative traversal with a pointer to the current node and track previously visited node to decide traversal direction.

Solution

1. Step 1: Understand traversal constraints

   Without left/right child pointers, Morris traversal is not applicable since it relies on child links.

2. Step 2: Use parent pointers to simulate traversal

   By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Tracking previous node enables correct traversal without extra space [OK]

Hint: Parent pointers + prev node tracking enable traversal [OK]

Common Mistakes:

• Trying to create threads on parent pointers
• Using recursion without child pointers
• Confusing BFS with inorder traversal