Binary Tree Inorder Traversal

▶

Steps

setup

Initialize current to root

Set current pointer to the root node (value 1). The result list is empty at this point.

💡 Starting at the root is essential to begin traversal from the top of the tree.

Line:

result = []
current = root

💡 The traversal begins at the root node with no nodes visited yet.

compare

Check if current.left is null

Current node (1) has no left child, so we will visit it and move to its right child.

💡 Nodes without left children can be visited immediately in inorder traversal.

Line:

if not current.left:

💡 Visiting nodes without left children first simplifies traversal.

fill_cells

Visit current node and move to right child

Append current node's value (1) to result and move current pointer to its right child (node 2).

💡 Visiting the node means adding its value to the output list in inorder sequence.

Line:

result.append(current.val)
current = current.right

💡 Visiting node 1 first because it has no left subtree.

compare

Current node has left child, find predecessor

Current node (2) has a left child (3). We start finding its inorder predecessor by setting predecessor to current.left.

💡 The predecessor is the rightmost node in the left subtree, used to create a thread.

Line:

predecessor = current.left

💡 Identifying the predecessor is key to threading the tree for traversal.

compare

Check predecessor.right for thread or move right

Check if predecessor (3) has a right child and if it points back to current (2). It does not, so we will create a thread.

💡 If predecessor.right is null, we create a thread to current to return after left subtree is done.

Line:

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

💡 Creating a thread allows traversal to return to current after left subtree.

insert

Create thread from predecessor.right to current

Set predecessor.right to current (2), creating a temporary thread to return after left subtree traversal. Then move current to its left child (3).

💡 Threading avoids recursion or stack by linking predecessor back to current.

Line:

predecessor.right = current
current = current.left

💡 Thread creation enables traversal of left subtree first.

compare

Current node (3) has no left child, visit it

Current node (3) has no left child, so we visit it and move current to its right child, which is a thread pointing back to node 2.

💡 Visiting nodes without left children is straightforward in inorder traversal.

Line:

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

💡 Visiting node 3 before returning to node 2 via thread.

compare

Thread detected, remove it and visit current

Current is back at node 2 via thread from predecessor.right. Since predecessor.right points to current, remove the thread and visit current.

💡 Removing the thread restores the original tree structure after left subtree traversal.

Line:

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

💡 Thread removal signals completion of left subtree and visiting current node.

traverse

Traversal complete, current is null

Current pointer is now null, indicating traversal is finished. The result contains the inorder sequence.

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

Line:

while current:
    ...
return result

💡 The algorithm successfully visited all nodes in inorder without recursion or stack.

return

Return the final inorder traversal result

The algorithm returns the result list containing the inorder traversal sequence [1, 3, 2].

💡 Returning the result completes the traversal process and provides the output.

Line:

return result

💡 The final output confirms the correctness of the Morris inorder traversal.

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 inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []  # STEP 1
    current = root  # STEP 1
    while current:  # STEP 2
        if not current.left:  # STEP 2
            result.append(current.val)  # STEP 3,7
            current = current.right  # STEP 3,7
        else:
            predecessor = current.left  # STEP 4
            while predecessor.right and predecessor.right != current:  # STEP 5
                predecessor = predecessor.right  # STEP 5
            if not predecessor.right:  # STEP 5
                predecessor.right = current  # STEP 6
                current = current.left  # STEP 6
            else:
                predecessor.right = None  # STEP 8
                result.append(current.val)  # STEP 8
                current = current.right  # STEP 8
    return result  # STEP 9

if __name__ == '__main__':
    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    print(inorderTraversal(root))  # Expected output: [1,3,2]

📊

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

Watching each step shows how the algorithm cleverly creates and removes threads to traverse the tree in order without extra space.

Current node: 1

123

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 (left_done)predecessor=3

Result: [1]

Current node: 3

123

DFS Stack

2 (left_done)predecessor=3

Result: [1]

Current node: 2

123

DFS Stack

2 (left_done)predecessor=3

Result: [1, 3]

123

Result: [1, 3, 2]

123

Result: [1, 3, 2]

123

Result: [1, 3, 2]

Return: [1,3,2]

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 thread creation and removal are subtle and happen dynamically.

✓ Nodes without left children are visited immediately, simplifying traversal steps.

Understanding this helps learners see why some nodes are visited right away and others require threading.

✓ Thread removal signals completion of left subtree traversal and triggers visiting the current node.

This concrete example clarifies the key decision point where traversal switches from left subtree to root.

Practice

1. Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below? Tree structure:

    1
   / \
  2   3

def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                predecessor.right = None
                current = current.right
    return result

easy

A. [2, 1, 3]

B. [1, 2, 3]

C. [1, 3, 2]

D. [3, 1, 2]

Solution

1. Step 1: Trace first iteration with current=1

   Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.

2. Step 2: Trace second iteration with current=2

   Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).

3. Step 3: Detect thread at 2.right=1

   Since predecessor.right == current, reset 2.right=None, move current=1.right=3.

4. Step 4: Trace current=3

   Node 3 has no left child, append 3, move current=3.right=None, loop ends.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Output matches preorder traversal [1,2,3] [OK]

Hint: Morris preorder appends root before left subtree [OK]

Common Mistakes:

• Appending nodes in wrong order
• Not resetting threaded links
• Confusing left and right child traversal

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

1. Step 1: Initialize variables

   inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).

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

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

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.

5. Final Answer:

   Option D -> Option D

6. 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]

3. You are given a binary tree where each node contains a non-negative integer value. You want to maximize the sum of values you can collect by selecting nodes such that no two directly connected nodes (parent-child) are both selected. Which approach guarantees an optimal solution for this problem?

easy

A. Use a greedy algorithm that always picks the node with the highest value first.

B. Use a depth-first search with dynamic programming that returns two values per node: max if robbing it and max if not robbing it.

C. Use a breadth-first search to select nodes level by level, picking the maximum values at alternate levels.

D. Use a brute force recursion that tries all subsets of nodes without any memoization.

Solution

1. Step 1: Understand the problem constraints

   The problem requires selecting nodes in a tree such that no parent and child are both selected, maximizing the sum of selected nodes.

2. Step 2: Identify the suitable algorithmic pattern

   A greedy or BFS level-based approach fails because the tree structure and adjacency constraints are complex. Brute force is correct but inefficient. The optimal solution uses DFS with DP returning two values per node: max if robbing it and max if not robbing it, ensuring all subproblems are solved optimally.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DFS with two-value DP handles adjacency constraints correctly [OK]

Hint: Tree + no adjacent nodes -> DFS with two-value DP [OK]

Common Mistakes:

• Assuming greedy or level-based selection works
• Trying brute force without memoization

4. You are given a binary tree and two nodes within it. You need to find the node that is the deepest common ancestor of both nodes. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Use a brute force approach by finding paths from root to each node and then comparing the paths.

B. Build a parent pointer map for all nodes, then use ancestor sets to find the lowest common ancestor.

C. Apply a greedy algorithm that picks the first common node found during a preorder traversal.

D. Use dynamic programming to store results of subtrees and combine them to find the ancestor.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the lowest common ancestor efficiently, ideally in O(n) time and O(n) space.

2. Step 2: Evaluate approaches

   Brute force (A) is correct but less optimal. Greedy (C) fails because it may pick incorrect ancestors. DP (D) is not applicable here. Building parent pointers and using ancestor sets (B) provides an optimal and clean solution.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Parent pointer + ancestor set approach is standard optimal solution [OK]

Hint: Parent pointers + ancestor sets yield optimal LCA solution [OK]

Common Mistakes:

• Assuming greedy traversal finds correct LCA
• Using DP where not applicable
• Brute force is optimal

5. Suppose you want to invert a binary tree where nodes can have an arbitrary number of children (not just two). Which modification to the inversion algorithm correctly generalizes the inversion to this n-ary tree?

hard

A. Swap only the first and last child pointers recursively, leaving others unchanged.

B. Use BFS to swap children pairwise at each level without recursion.

C. Recursively invert each child's subtree, then reverse the list of children in-place.

D. Invert only the leftmost and rightmost subtrees recursively, ignoring middle children.

Solution

1. Step 1: Understand inversion for binary tree swaps left and right children

   For n-ary trees, inversion means reversing the order of children after inverting each child's subtree.

2. Step 2: Generalize recursion and reversal

   Recursively invert each child's subtree, then reverse the children list to mirror the tree structure.

3. Step 3: Evaluate other options

   Swapping only first and last or partial BFS swaps do not fully invert the tree structure.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Recursion plus reversing children list generalizes inversion correctly [OK]

Hint: Invert subtrees recursively, then reverse children list for n-ary trees [OK]

Common Mistakes:

• Swapping only some children pairs
• Ignoring recursion on all children
• Using BFS without recursion for full inversion