Construct Tree from Inorder and Postorder

▶

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.

fill_cells

Process next postorder element: 20

Create a new node with value 20 from postorder[-2]. Compare top of stack (3) with inorder[inorder_index] (7). Since 3 != 7, attach 20 as right child of 3 and push 20 onto stack.

💡 This step shows how right children are attached when the top of stack does not match inorder at current index.

Line:

node_val = postorder[i]
node = TreeNode(node_val)
top = stack[-1]
if top.val != inorder[inorder_index]:
    top.right = node
    stack.append(node)

💡 Right subtree nodes are added first when inorder and stack top differ.

fill_cells

Process next postorder element: 7

Create node 7 from postorder[-3]. Top of stack is 20, which is not equal to inorder[inorder_index] (7). Attach 7 as right child of 20 and push 7 onto stack.

💡 Continuing to add right children as long as top of stack differs from inorder at current index.

Line:

node_val = postorder[i]
node = TreeNode(node_val)
top = stack[-1]
if top.val != inorder[inorder_index]:
    top.right = node
    stack.append(node)

💡 Right subtree is extended deeper before backtracking.

compare

Process next postorder element: 15

Create node 15 from postorder[-4]. Now top of stack is 7, which equals inorder[inorder_index] (7). Begin popping from stack while top matches inorder at inorder_index.

💡 This step shows the key backtracking: when top of stack matches inorder, we pop to move left in the tree.

Line:

while stack and stack[-1].val == inorder[inorder_index]:
    top = stack.pop()
    inorder_index -= 1

💡 Matching inorder values indicate completed right subtree; time to attach left child.

compare

Continue popping stack for inorder match

Top of stack is now 20, which equals inorder[inorder_index] (20). Pop 20 and decrement inorder_index to 2.

💡 Continuing to pop stack nodes that match inorder to backtrack correctly.

Line:

while stack and stack[-1].val == inorder[inorder_index]:
    top = stack.pop()
    inorder_index -= 1

💡 Backtracking continues until top of stack no longer matches inorder.

fill_cells

Attach 15 as left child of 20

After popping, top of stack is 3 which does not equal inorder[inorder_index] (15). Attach 15 as left child of last popped node (20) and push 15 onto stack.

💡 This step attaches a left child after backtracking, showing how left subtrees are built.

Line:

top.left = node
stack.append(node)

💡 Left children are attached after popping nodes matching inorder.

fill_cells

Process next postorder element: 9

Create node 9 from postorder[-5]. Top of stack is 15, which equals inorder[inorder_index] (15). Begin popping from stack while top matches inorder at inorder_index.

💡 This step shows the key backtracking again: when top of stack matches inorder, pop to move left in the tree.

Line:

while stack and stack[-1].val == inorder[inorder_index]:
    top = stack.pop()
    inorder_index -= 1

💡 Correctly identifying when to pop stack nodes to attach left children is crucial for accurate tree reconstruction.

fill_cells

Pop stack and attach 9 as left child

Attach 9 as left child of last popped node (15) and push 9 onto stack.

💡 This step shows attaching left child after popping nodes matching inorder.

Line:

top.left = node
stack.append(node)

💡 Left children are attached after backtracking from matching inorder nodes.

compare

Pop stack and attach left subtree complete

Top of stack is 9, which equals inorder[inorder_index] (9). Pop 9 and decrement inorder_index to 1. Then top is 3, which equals inorder[inorder_index] (3). Pop 3 and decrement inorder_index to -1.

💡 Final backtracking steps to complete tree construction.

Line:

while stack and stack[-1].val == inorder[inorder_index]:
    top = stack.pop()
    inorder_index -= 1

💡 Backtracking finishes when all inorder nodes matched and popped.

reconstruct

Return constructed tree root

All nodes processed and stack is empty. Return the root node (3) which now has left and right subtrees attached correctly.

💡 This final step confirms the tree is fully constructed and ready for use.

Line:

return root

💡 The root node represents the fully reconstructed binary tree.

from typing import List, Optional

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

def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    if not inorder or not postorder:
        return None
    stack = []  # STEP 1
    root_val = postorder[-1]  # STEP 1
    root = TreeNode(root_val)  # STEP 1
    stack.append(root)  # STEP 1
    inorder_index = len(inorder) - 1  # STEP 1

    for i in range(len(postorder) - 2, -1, -1):  # STEP 2 to 9
        node_val = postorder[i]  # STEP 2
        node = TreeNode(node_val)  # STEP 2
        top = stack[-1]  # STEP 2
        if top.val != inorder[inorder_index]:  # STEP 2,3
            top.right = node  # STEP 2,3
            stack.append(node)  # STEP 2,3
        else:
            while stack and stack[-1].val == inorder[inorder_index]:  # STEP 4,5,9
                top = stack.pop()  # STEP 4,5,9
                inorder_index -= 1  # STEP 4,5,9
            top.left = node  # STEP 6,8
            stack.append(node)  # STEP 6,8
    return root  # STEP 10

📊

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.

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. 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. Consider the following iterative postorder traversal code to compute the diameter of a binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final value of the variable diameter after the function completes?

easy

A. 2

B. 4

C. 1

D. 3

Solution

1. Step 1: Trace heights and diameter updates for each node.

   Node 4: height=1, diameter=0; Node 2: left=1 (node4), right=0, diameter=max(0,1)=1; Node 3: height=1, diameter=1; Node 1: left=2 (node2), right=1 (node3), diameter=max(1,2+1=3)=3.

2. Step 2: Verify final diameter value returned.

   The diameter is the maximum sum of left and right heights at any node, which is 3 edges, so the longest path length is 3 edges.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Longest path is from node 4 to node 3 with length 3 edges [OK]

Hint: Diameter counts edges, not nodes [OK]

Common Mistakes:

• Confusing diameter as number of nodes
• Off-by-one in height calculation
• Missing right subtree height

3. Consider the following Python code implementing the optimal flatten function for a binary tree. Given the input tree: 1 / \ 2 3 What is the value of the global variable prev after the call flatten(root) completes?

easy

A. TreeNode with val=3

B. TreeNode with val=1

C. TreeNode with val=2

D. None

Solution

1. Step 1: Trace flatten calls on root=1

   flatten(1) calls flatten(3) then flatten(2). After flatten(3), prev=TreeNode with val=3; after flatten(2), prev=TreeNode with val=2; finally, root=1 sets root.right=prev (2) and prev=TreeNode with val=1.

2. Step 2: Final value of prev after flatten(1)

   After processing root=1, prev points to the root node with val=1.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Global prev ends at root node after full traversal [OK]

Hint: Global prev ends at root after full flatten [OK]

Common Mistakes:

• Assuming prev ends at last leaf node
• Confusing order of recursive calls
• Forgetting prev is updated after rewiring

4. Examine the following buggy code for the Path Sum problem. Which line contains the subtle bug that causes incorrect results on some inputs?

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if curr_sum == targetSum:  # Bug here
            return True
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)

medium

A. Line 3: if not node: return False

B. Line 6: if curr_sum == targetSum:

C. Line 8: return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)

D. Line 5: curr_sum += node.val

Solution

1. Step 1: Understand leaf node condition

   The sum should be checked only at leaf nodes, not at every node.

2. Step 2: Identify the bug

   Line 6 checks sum at any node, causing premature True returns for partial paths.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bug causes incorrect True if partial path sum equals targetSum [OK]

Hint: Sum check must be at leaf nodes only [OK]

Common Mistakes:

• Checking sum at internal nodes
• Not handling null root

5. What is the time complexity of the BFS-based serialization and deserialization of a binary tree with n nodes, assuming the tree is balanced? Consider both serialization and deserialization separately.

medium

A. Serialization: O(n log n), Deserialization: O(n log n)

B. Serialization: O(n), Deserialization: O(n^2)

C. Serialization: O(n), Deserialization: O(n)

D. Serialization: O(n^2), Deserialization: O(n)

Solution

1. Step 1: Analyze serialization time

   Each node is enqueued and dequeued exactly once, so serialization is O(n).

2. Step 2: Analyze deserialization time

   Deserialization processes each node once, reconstructing the tree in O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both serialization and deserialization scale linearly with number of nodes [OK]

Hint: Each node is processed once in BFS serialization/deserialization [OK]

Common Mistakes:

• Assuming deserialization is O(n^2) due to nested loops
• Confusing tree height with number of nodes
• Thinking serialization is O(n log n) due to queue operations