Binary Tree Postorder Traversal

▶

Steps

setup

Initialize variables for traversal

We start by initializing the result list, an empty stack, last_visited pointer as None, and set current to the root node (value 1).

💡 Setting up these variables prepares the algorithm to simulate recursion iteratively.

Line:

result = []
stack = []
last_visited = None
current = root

💡 These variables track the traversal progress: stack for nodes to revisit, current for exploration, and last_visited to avoid revisiting right subtrees.

fill_cells

Push current node (1) and move left

Current node 1 is pushed onto the stack. Since it has no left child, current moves to None.

💡 Pushing nodes while moving left simulates recursive calls going down the left subtree.

Line:

while current:
    stack.append(current)
    current = current.left

💡 We push node 1 to revisit it after its left subtree is processed.

compare

Peek top node (1) and check right child

Peek at the top of the stack, node 1. It has a right child (node 2) that has not been visited yet, so we set current to node 2 to traverse its subtree.

💡 Checking the right child ensures we traverse right subtrees before visiting the node itself.

Line:

peek_node = stack[-1]
if peek_node.right and last_visited != peek_node.right:
    current = peek_node.right

💡 We delay visiting node 1 until its right subtree is fully traversed.

fill_cells

Push current node (2) and move left

Current node 2 is pushed onto the stack. We move current to its left child, node 3, to continue traversing left.

💡 Continuing to push left children simulates recursive descent down the left subtree.

Line:

while current:
    stack.append(current)
    current = current.left

💡 Node 2 is now on the stack waiting for its left subtree to be processed.

fill_cells

Push current node (3) and move left (None)

Current node 3 is pushed onto the stack. It has no left child, so current moves to None.

💡 Leaf nodes are pushed and then current becomes None, triggering the visit or right subtree check.

Line:

while current:
    stack.append(current)
    current = current.left

💡 Node 3 is now the top of the stack, ready to be visited or to check right subtree.

compare

Peek top node (3), no right child, visit node

Peek at node 3 on top of the stack. It has no right child, so we visit it by appending its value to result and pop it from the stack.

💡 Visiting nodes happens only after left and right subtrees are fully processed.

Line:

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()

💡 Node 3 is the leftmost leaf and is visited first in postorder.

compare

Peek top node (2), no right child unvisited, visit node

Peek at node 2 on top of the stack. It has no right child unvisited (right is None), so we visit node 2 and pop it from the stack.

💡 After left subtree is visited, if no right subtree exists or is visited, we visit the node itself.

Line:

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()

💡 Node 2 is visited after its left subtree (node 3) is done.

compare

Peek top node (1), right child visited, visit node

Peek at node 1 on top of the stack. Its right child (node 2) was last visited, so we visit node 1 and pop it from the stack.

💡 We visit the root node only after both left and right subtrees are fully visited.

Line:

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()

💡 Node 1 is visited last, completing the postorder traversal.

reconstruct

Traversal complete, return result

Stack is empty and current is None, so traversal is complete. The result list [3, 2, 1] is returned as the postorder traversal.

💡 Returning the result finalizes the traversal and provides the output.

Line:

return result

💡 The traversal order matches the expected postorder sequence.

summary

Summary and final notes

The iterative postorder traversal is complete. The stack is empty, and the result contains the nodes in postorder: left subtree, right subtree, then root.

💡 This final step reinforces the traversal order and the role of the stack and last_visited pointer.

💡 Understanding the stack and last_visited pointer is key to mastering iterative postorder 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 postorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []  # STEP 1: Initialize result list
    stack = []   # STEP 1: Initialize empty stack
    last_visited = None  # STEP 1: Track last visited node
    current = root  # STEP 1: Start from root

    while current or stack:  # STEP 2: Continue while nodes remain
        while current:  # STEP 4: Traverse left subtree
            stack.append(current)  # STEP 4: Push current node
            current = current.left  # STEP 4: Move left

        peek_node = stack[-1]  # STEP 6: Peek top node
        if peek_node.right and last_visited != peek_node.right:  # STEP 7: Check right child
            current = peek_node.right  # STEP 7: Move to right child
        else:
            result.append(peek_node.val)  # STEP 8: Visit node
            last_visited = stack.pop()  # STEP 8: Pop node

    return result  # STEP 9: Return final traversal result

📊

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

Watching each step of the traversal helps you understand how the algorithm simulates recursion using a stack and tracks last visited nodes to decide when to visit or traverse right subtrees.

Current node: 1

123

123

DFS Stack

1 (entered)

Current node: 2

123

DFS Stack

1 (left_done)

Current node: 3

123

DFS Stack

2 (entered)1 (left_done)

123

DFS Stack

3 (entered)2 (entered)1 (left_done)

123

DFS Stack

2 (entered)1 (left_done)

Result: [3]

123

DFS Stack

1 (left_done)

Result: [3, 2]

123

Result: [3, 2, 1]

123

Result: [3, 2, 1]

Return: [3,2,1]

123

Result: [3, 2, 1]

Return: [3,2,1]

Key Takeaways

✓ The algorithm uses a stack and a last_visited pointer to simulate recursion and ensure nodes are visited after their subtrees.

This insight is hard to see from code alone because the interplay between stack and last_visited is subtle and critical for correct postorder.

✓ Nodes are pushed while traversing left, and only visited after both left and right subtrees are processed.

Visualizing the stack growing and shrinking clarifies the traversal order dependency.

✓ The decision to move to the right child or visit the node depends on whether the right subtree has been visited, tracked by last_visited.

Seeing this decision in action helps understand why the algorithm avoids revisiting nodes prematurely.

Practice

1. Consider the following iterative postorder traversal code to check if a binary tree is balanced. Given the tree: root=1, left=2, right=3, and node 2 has left child 4. What is the value of heights[root] after the traversal completes?

easy

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace heights for leaf nodes

   Node 4 is a leaf, so heights[4] = 1.

2. Step 2: Compute heights bottom-up

   Node 2 has left child 4 (height 1) and no right child (height 0), so heights[2] = 1 + max(1,0) = 2. Node 3 is leaf, heights[3] = 1. Root 1 has children heights 2 and 1, so heights[1] = 1 + max(2,1) = 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Height of root is max height of subtrees plus one [OK]

Hint: Height of root equals max subtree height plus one [OK]

Common Mistakes:

• Forgetting to add 1 for current node height
• Mixing up left and right subtree heights
• Returning height instead of boolean balance

2. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?

medium

A. Line creating root node with postorder[-1]

B. Line initializing inorder_index to 0

C. Line attaching node as right child

D. Line popping from stack inside while loop

Solution

1. Step 1: Identify inorder_index initialization

   inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.

2. Step 2: Consequences of wrong initialization

   Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct inorder_index initialization is critical for stack popping logic [OK]

Hint: inorder_index must start at last index, not zero [OK]

Common Mistakes:

• Wrong inorder_index initialization
• Confusing postorder traversal direction
• Incorrect stack popping conditions

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

1. Step 1: Understand binary search condition

   The condition should be 'if idx <= mid' to correctly include mid index in left subtree.

2. Step 2: Identify impact of bug

   Using 'idx < mid' excludes mid index from left subtree, causing incorrect traversal and wrong node existence checks.

3. Final Answer:

   Option A -> Option A

4. 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. Suppose the problem changes: the binary tree is no longer complete but only a general binary tree. Which of the following statements about counting nodes efficiently is true?

hard

A. Breadth-first search (BFS) can count nodes in O(log n) time for any binary tree.

B. The optimal binary search approach on the last level still applies with minor modifications.

C. Using tree height to check perfect subtrees can still reduce time complexity to O((log n)^2).

D. A simple DFS traversal counting all nodes is the only guaranteed correct method with O(n) time.

Solution

1. Step 1: Understand the problem change

   The tree is no longer complete, so properties used by optimal methods do not hold.

2. Step 2: Identify correct counting method

   Only a full traversal (DFS or BFS) guarantees counting all nodes correctly in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal methods rely on completeness, which is lost here [OK]

Hint: Without completeness, must traverse all nodes [OK]

Common Mistakes:

• Trying to apply binary search on last level
• Assuming height checks still reduce complexity

5. Suppose the binary tree nodes can have negative values and you want to find the diameter defined as the longest path in terms of number of edges (ignoring node values). Which modification to the standard diameter algorithm is necessary to handle this variant correctly?

hard

A. No modification needed; the standard diameter algorithm based on heights works regardless of node values.

B. Modify the algorithm to sum node values along paths and find maximum sum path instead of longest path.

C. Change the height calculation to ignore negative nodes by treating them as null nodes.

D. Use breadth-first search to find the longest path instead of depth-first traversal.

Solution

1. Step 1: Recognize diameter depends on path length (edges), not node values.

   Negative values do not affect height or path length calculations.

2. Step 2: Confirm standard height-based diameter algorithm works unchanged.

   Heights and diameter calculations rely on structure, so no changes are needed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diameter depends on edges, not node values [OK]

Hint: Diameter is structural, unaffected by node values [OK]

Common Mistakes:

• Confusing diameter with max sum path
• Ignoring negative nodes incorrectly
• Switching to BFS unnecessarily