Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonMicrosoftGoogle

Construct Tree from Inorder and Postorder

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize stack and root node

Start by creating the root node from the last element of postorder (3). Push it onto the stack. Set inorder_index to the last index of inorder (4).

💡 This sets the foundation: the root is always the last postorder element, and the stack will help track nodes to attach children.
Line:root_val = postorder[-1] root = TreeNode(root_val) stack.append(root) inorder_index = len(inorder) - 1
💡 Root node identified and stack initialized to manage subtree construction.
📊
Construct Tree from Inorder and Postorder - Watch the Algorithm Execute, Step by Step
Watching this step-by-step reveals how the stack helps reconstruct the tree without recursion, clarifying the relationship between inorder and postorder traversals.
Step 1/10
·Active fill★Answer cell
Current node: 0
3
Current node: 1
320
Current node: 2
3207
Current node: 3
320715
Current node: 3
320715
Current node: 3
320715
Current node: 4
3207159
Current node: 4
3207159
3207159
Current node: 0
3207159
Return: 0

Key Takeaways

✓ The last element in postorder is always the root, which anchors the entire tree construction.

This is fundamental but often overlooked; seeing it visually helps cement this root identification.

✓ The stack tracks nodes whose subtrees are not fully constructed, enabling iterative backtracking instead of recursion.

Understanding how the stack simulates recursion clarifies the algorithm's flow and why nodes are popped when inorder matches.

✓ When the top of the stack matches the current inorder element, it signals completion of the right subtree and triggers attaching left children.

This decision point is subtle in code but critical; the visualization makes it explicit and easy to follow.

Practice

(1/5)
1. You need to determine if a binary tree is height-balanced, meaning the heights of the two child subtrees of any node never differ by more than one. Which approach guarantees an optimal O(n) time solution without redundant height computations?
easy
A. Use a top-down recursive approach that checks balance only at the root node.
B. Compute height for each node separately and check balance at each node recursively.
C. Perform a breadth-first traversal and check balance by comparing subtree sizes at each level.
D. Use a postorder traversal that returns height and balance status simultaneously, stopping early if imbalance is found.

Solution

  1. Step 1: Understand the problem constraints

    The problem requires checking balance at every node efficiently without recomputing heights multiple times.
  2. Step 2: Identify the approach that avoids redundant work

    Postorder traversal that returns both height and balance status in one pass allows early exit on imbalance and avoids repeated height calculations.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Postorder traversal with early exit is O(n) and avoids recomputation [OK]
Hint: Postorder traversal with early exit avoids repeated height calls [OK]
Common Mistakes:
  • Checking balance only at root misses subtree imbalances
  • Computing height separately for each node causes O(n²) time
  • Using BFS to check balance is incorrect as balance depends on subtree heights
2. Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?
def inorderTraversal(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                # BUG: missing line to remove thread
                result.append(current.val)
                current = current.right
    return result
medium
A. Missing line resetting predecessor.right = None to remove thread
B. Line moving current to current.left after creating thread
C. Line appending current.val after detecting thread
D. Line setting predecessor.right = current (creating thread)

Solution

  1. Step 1: Identify thread removal step

    Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.
  2. Step 2: Locate missing removal

    The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without removing thread, traversal loops endlessly [OK]
Hint: Always remove threads to restore tree [OK]
Common Mistakes:
  • Forgetting to remove thread
  • Appending node before removing thread
  • Incorrectly creating thread
3. Consider the following buggy code snippet for building a binary tree from preorder and inorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or infinite loops?
medium
A. Line where stack is initialized with root
B. Line inside if block missing stack.append(node.left)
C. Line where root is initialized with preorder[0]
D. Line inside else block where inorder_index is incremented

Solution

  1. Step 1: Identify missing operation

    Inside the if block, after creating node.left, the new node is not pushed onto the stack.
  2. Step 2: Consequences of missing stack append

    Without pushing, the algorithm loses track of the left subtree root, causing incorrect tree or infinite loops.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Stack must track all nodes to correctly build tree [OK]
Hint: Always push newly created nodes to stack to track subtree roots [OK]
Common Mistakes:
  • Forgetting to push left child nodes
  • Incorrectly incrementing inorder_index
  • Misinitializing root or stack
4. What is the time complexity of the optimal DFS with two-value return solution for the House Robber III problem on a tree with n nodes?
medium
A. O(n^2) due to checking grandchildren nodes explicitly
B. O(n) but with extra O(n) space for memoization arrays
C. O(n) because each node is visited once in DFS
D. O(n log n) because of recursive calls and combining results

Solution

  1. Step 1: Identify DFS traversal cost

    The algorithm visits each node exactly once in a postorder DFS traversal.
  2. Step 2: Analyze operations per node

    At each node, constant time operations are done: combining left and right child results, no repeated work.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Linear traversal of n nodes -> O(n) time [OK]
Hint: DFS visits each node once, no repeated subproblems [OK]
Common Mistakes:
  • Assuming O(n^2) due to grandchildren checks
  • Confusing recursion stack space with time complexity
5. The following code attempts to find the Lowest Common Ancestor using parent pointers. Identify the line containing the subtle bug that causes incorrect results when one node is ancestor of the other.
def lowestCommonAncestor(root, p, q):
    parent = {root: None}
    stack = [root]
    while p not in parent or q not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q
medium
A. Line: while p not in parent or q not in parent:
B. Line: while p:
C. Line: while q not in ancestors:
D. Line: parent = {root: None}

Solution

  1. Step 1: Analyze parent map construction loop

    The loop 'while p not in parent or q not in parent:' ensures both nodes are in the parent map before ancestor sets are built.
  2. Step 2: Identify subtle bug

    If one node is ancestor of the other, the loop may terminate prematurely if only one node is in parent map, causing KeyError later.
  3. Step 3: Explanation

    The bug is that the loop condition does not guarantee both nodes are fully processed in the parent map before ancestor traversal.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Loop condition must ensure both nodes are in parent map to avoid errors [OK]
Hint: Parent map construction loop must fully process both nodes [OK]
Common Mistakes:
  • Assuming parent map always complete
  • Ignoring incomplete parent map causing KeyError
  • Misplacing bug in ancestor set loops
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