Binary Tree Preorder Traversal

▶

Steps

setup

Initialize current to root and result to empty

Set current node to root (value 1) and initialize an empty list to store traversal result.

💡 Starting point: current points to root, no nodes visited yet.

Line:

result = []
current = root

💡 Traversal begins at root; result list is ready to collect node values.

compare

Current node 1 has no left child, visit and move right

Node 1 has no left child, so we visit it and move current to its right child (node 2).

💡 Nodes without left children are visited immediately in preorder traversal.

Line:

if current.left is None:
    result.append(current.val)
    current = current.right

💡 Visiting node 1 first matches preorder's 'visit node before children' rule.

compare

Current node 2 has a left child, start finding predecessor

Node 2 has a left child (3), so we start to find the rightmost node in its left subtree to identify the predecessor.

💡 Predecessor helps create a thread back to current for traversal without recursion.

Line:

predecessor = current.left

💡 Identifying the predecessor node is the first step to threading the tree.

compare

Move predecessor to rightmost node in left subtree

Check if predecessor's right child exists and is not current; if so, move predecessor to its right child to find the rightmost node.

💡 The rightmost node in left subtree is the predecessor for threading.

Line:

while predecessor.right and predecessor.right != current:
    predecessor = predecessor.right

💡 Looping to find the predecessor ensures correct threading point.

insert

Predecessor's right is null, create thread and visit current

Predecessor (3) has no right child, so we create a thread from predecessor.right to current (2), visit current, and move current to left child.

💡 Threading allows returning to current after left subtree traversal.

Line:

if predecessor.right is None:
    predecessor.right = current
    result.append(current.val)
    current = current.left

💡 Threading is established and current node (2) is visited before going left.

compare

Current node 3 has no left child, visit and move right (thread)

Node 3 has no left child, so we visit it and move current to its right child, which is a thread back to 2.

💡 Nodes without left children are visited immediately, and threads guide traversal back.

Line:

if current.left is None:
    result.append(current.val)
    current = current.right

💡 Visiting leaf node 3 and following thread back to 2 continues traversal.

delete

Back at node 2, predecessor's right points to current, remove thread

Back at node 2, predecessor (3) has right pointer to current (2), indicating a thread to revert. We remove the thread.

💡 Thread presence means left subtree is fully traversed; time to remove thread.

Line:

if predecessor.right == current:
    predecessor.right = None

💡 Removing thread restores original tree structure.

traverse

Move current to right child of node 2

After removing the thread, move current to the right child of node 2, which is null.

💡 Moving to right child continues traversal after left subtree is done.

Line:

current = current.right

💡 Traversal proceeds to right subtree or ends if null.

traverse

Current is null, traversal complete

Current node is null, indicating traversal is complete and all nodes have been visited.

💡 Traversal ends when there are no more nodes to visit.

Line:

while current:
    ...
return result

💡 Algorithm successfully visited all nodes in preorder without recursion or stack.

from typing import Optional, List

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

def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []  # STEP 1: Initialize result list
    current = root  # STEP 1: Start at root
    while current:  # STEP 9: Loop until current is None
        if current.left is None:  # STEP 2 & 6: No left child, visit and move right
            result.append(current.val)  # STEP 2 & 6: Visit current
            current = current.right  # STEP 2 & 6: Move to right child
        else:
            predecessor = current.left  # STEP 3: Find predecessor
            while predecessor.right and predecessor.right != current:  # STEP 4: Move to rightmost
                predecessor = predecessor.right
            if predecessor.right is None:  # STEP 5: Create thread and visit
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:  # STEP 7 & 8: Thread exists, remove and move right
                predecessor.right = None
                current = current.right
    return result  # STEP 9: Return final preorder list

📊

Binary Tree Preorder Traversal - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the algorithm cleverly uses tree threading to avoid extra space, making preorder traversal efficient and elegant.

Current node: 1

123

Current node: 2

123

Result: [1]

Current node: 2

123

DFS Stack

2 (entered)predecessor=3

Result: [1]

Current node: 2

123

DFS Stack

2 (entered)predecessor=3

Result: [1]

Current node: 3

123

DFS Stack

2 (left_done)predecessor=3

Result: [1, 2]

Current node: 2

123

Result: [1, 2, 3]

Current node: 2

123

Result: [1, 2, 3]

123

Result: [1, 2, 3]

123

Result: [1, 2, 3]

Return: [1,2,3]

Key Takeaways

✓ Morris traversal uses temporary threads to traverse the tree without recursion or stack.

This insight is hard to see from code alone because the pointer changes are subtle and temporary.

✓ Nodes are visited before traversing left subtree, matching preorder order exactly.

Visualizing the visit order clarifies why the algorithm appends node values at specific steps.

✓ Threads are created and removed dynamically to simulate recursion return points.

Seeing when and why threads are added or removed helps understand the traversal flow control.

Practice

1. What is the time complexity of the Morris inorder traversal algorithm on a binary tree with n nodes?

medium

A. O(n) because each edge is visited at most twice during threading and unthreading.

B. O(n \times h) where h is tree height due to repeated traversal of left subtrees.

C. O(n \log n) due to repeated searching for predecessors.

D. O(n^2) in worst case when tree is skewed and predecessor search is costly.

Solution

1. Step 1: Analyze predecessor visits

   Each node's left subtree is traversed to find the predecessor, which can take up to h steps where h is the height of the tree.

2. Step 2: Count total operations

   In skewed trees, this leads to O(n x h) time complexity due to repeated traversal of left subtrees.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case time complexity is O(n x h) [OK]

Hint: Predecessor search can take O(h) per node in skewed trees [OK]

Common Mistakes:

• Assuming predecessor search is O(1) per node
• Confusing threading effect with total complexity
• Ignoring skewed tree worst case

2. Consider this buggy iterative postorder traversal code:

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited == peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

What is the bug in this code?

medium

A. The inner while loop should traverse right children instead of left

B. The condition should check if last_visited != peek_node.right, not == peek_node.right

C. The last_visited variable is never updated

D. The result list is appended before traversing the left subtree

Solution

1. Step 1: Examine condition for traversing right subtree

   Correct logic requires moving to right child if it exists and was not visited yet, so condition must be last_visited != peek_node.right.

2. Step 2: Identify effect of wrong condition

   Using last_visited == peek_node.right causes skipping right subtree traversal or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing condition restores correct postorder traversal [OK]

Hint: Check last_visited != right child to avoid revisiting [OK]

Common Mistakes:

• Using == instead of !=
• Not updating last_visited
• Appending too early

3. What is the time complexity of the optimal countNodes algorithm that uses binary search on the last level of a complete binary tree with n nodes?

medium

A. O(log n)

B. O(n)

C. O((log n)^2)

D. O(n log n)

Solution

1. Step 1: Analyze height and binary search

   Height h = O(log n). Binary search on last level does O(log n) steps.

2. Step 2: Combine existence checks

   Each existence check traverses height h = O(log n). Total time = O(log n) * O(log n) = O((log n)^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested log factors from height and binary search [OK]

Hint: Two nested log factors multiply to (log n)^2 [OK]

Common Mistakes:

• Confusing O(log n) with O((log n)^2)
• Assuming linear time due to traversal

4. What is the space complexity of the optimal in-place flatten algorithm that uses reverse preorder traversal with a global pointer on a binary tree of n nodes and height h?

medium

A. O(n) due to storing all nodes in a list during traversal

B. O(1) because the algorithm modifies the tree in-place without extra memory

C. O(log n) because the tree height is always balanced and recursion stack is limited

D. O(h) due to recursion stack depth in worst case of skewed tree

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.

2. Step 2: Clarify why O(h) not O(1) or O(n)

   It does not store nodes externally (not O(n)) and is not constant space due to recursion stack (not O(1)). For skewed trees, h can be up to n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack space equals tree height h [OK]

Hint: Recursion stack space equals tree height h [OK]

Common Mistakes:

• Assuming O(1) space because of in-place modification
• Confusing recursion stack with explicit data structures
• Assuming balanced tree always so O(log n) space

5. The following code attempts to count the number of paths summing to targetSum using iterative DFS and prefix sums. Which line contains a subtle bug that causes incorrect path counts?

class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}
        result = 0
        stack = [(root, 0, False)]  # node, current_sum, visited_children

        while stack:
            node, current_sum, visited = stack.pop()
            if node is None:
                continue
            if not visited:
                current_sum += node.val
                result += prefix_counts.get(current_sum - targetSum, 0)
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
                stack.append((node, current_sum, True))  # Mark node as visited
                stack.append((node.right, current_sum, False))
                stack.append((node.left, current_sum, False))
            else:
                # BUG: Missing decrement of prefix_counts on backtrack
                # prefix_counts[current_sum] -= 1
                pass

        return result

medium

A. Line where prefix_counts[current_sum] should be decremented but is missing

B. Line where prefix_counts[current_sum] is incremented

C. Line where current_sum is incremented by node.val

D. Line where stack appends left and right children

Solution

1. Step 1: Identify prefix_counts usage

   prefix_counts tracks how many times a prefix sum has occurred along the current path.

2. Step 2: Recognize missing decrement on backtrack

   Failing to decrement prefix_counts[current_sum] when backtracking causes counts to accumulate incorrectly across branches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing decrement leads to overcounting paths [OK]

Hint: Always decrement prefix_counts on backtrack [OK]

Common Mistakes:

• Not decrementing prefix_counts after visiting children
• Assuming prefix_counts only grows
• Confusing when to mark node as visited