Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoft

Binary Tree Postorder Traversal

Choose your preparation mode4 modes available
▶
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.
📊
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.
Step 1/10
·Active fill★Answer cell
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/5)
1. You need to output the values of a binary tree's nodes in the order: left subtree, node itself, then right subtree, without modifying the tree structure or using extra space proportional to the tree height. Which approach best fits this requirement?
easy
A. Use a breadth-first search (BFS) to visit nodes level by level.
B. Use a recursive preorder traversal that visits root, left, then right nodes.
C. Use Morris traversal to perform inorder traversal with O(1) extra space by temporarily modifying tree links.
D. Use a dynamic programming approach to store and reuse subtree results.

Solution

  1. Step 1: Understand traversal order requirement

    Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.
  2. Step 2: Identify approach with O(1) space

    Morris traversal achieves inorder traversal without recursion or stack by temporarily modifying tree pointers, restoring them after use.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Morris traversal is known for O(1) space inorder traversal [OK]
Hint: Morris traversal enables inorder with O(1) space [OK]
Common Mistakes:
  • Confusing preorder with inorder traversal order
  • Assuming BFS can produce inorder sequence
  • Thinking DP applies to traversal order
2. 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
3. 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
4. Suppose the problem is modified so that you can rob the same node multiple times (i.e., nodes can be reused any number of times), but still cannot rob directly connected nodes simultaneously. Which modification to the algorithm is necessary to correctly solve this variant?
hard
A. Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse.
B. Use the same DFS with two-value return; no changes needed since adjacency constraints remain.
C. Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection.
D. Modify the DFS to allow revisiting nodes multiple times and use memoization keyed by node and robbing state.

Solution

  1. Step 1: Understand the reuse constraint

    Allowing multiple robberies per node breaks the tree structure assumption and simple one-time visit DFS.
  2. Step 2: Identify necessary algorithmic change

    We must track states including how many times a node is robbed and ensure adjacency constraints per robbery. Memoization keyed by node and robbing state prevents exponential recomputation.
  3. Step 3: Why other options fail

    Use the same DFS with two-value return; no changes needed since adjacency constraints remain. ignores reuse; Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection. is overcomplicated and unnecessary since the structure is still a tree; Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse. is vague and does not address adjacency constraints properly.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Memoization with extended state handles reuse and adjacency constraints [OK]
Hint: Reuse requires stateful memoization, not simple DFS [OK]
Common Mistakes:
  • Assuming original DFS suffices for reuse
  • Ignoring adjacency constraints when reusing nodes
5. Suppose the problem is modified so that node values can be negative integers, and the goal remains to sum all root-to-leaf numbers formed by concatenation (including negative signs). Which of the following changes to the algorithm is necessary to handle this correctly?
hard
A. Skip negative nodes since they break number formation
B. Continue using integer arithmetic with multiplication by 10, ignoring signs
C. Add absolute values of node.val to current_number to avoid sign issues
D. Use string concatenation of node values along the path and convert to integer at leaf nodes

Solution

  1. Step 1: Understand impact of negative values

    Integer arithmetic with multiplication by 10 assumes digits 0-9; negative signs break this assumption.
  2. Step 2: Identify correct approach

    Concatenating node values as strings preserves negative signs and digit order; convert to integer only at leaf nodes.
  3. Step 3: Confirm other options fail

    Ignoring signs or skipping negatives leads to incorrect sums or incomplete paths.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    String concatenation handles negative digits correctly [OK]
Hint: Use string concatenation for negative digits [OK]
Common Mistakes:
  • Assuming all digits are positive
  • Using arithmetic without sign handling
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard