[Solved] In the following recursive function for building a binary tree from inorder and postorder traversals, which line contains a subtle bug that can cause incorrect tree construction or runtime errors?... | Tree: Depth-First Search

Tree: Depth-First Search - Construct Tree from Inorder and Postorder

In the following recursive function for building a binary tree from inorder and postorder traversals, which line contains a subtle bug that can cause incorrect tree construction or runtime errors?

def build(in_left, in_right, post_left, post_right):
    if in_left > in_right:
        return None
    root_val = postorder[post_right]
    root = TreeNode(root_val)
    index = inorder_index_map[root_val]
    left_tree_size = index - in_left
    root.left = build(in_left, index - 1, post_left, post_left + left_tree_size - 1)
    root.right = build(index + 1, in_right, post_left + left_tree_size, post_right - 1)
    return root

AThe recursive call for the right subtree uses incorrect postorder indices

BThe calculation of 'left_tree_size' is incorrect and should be 'in_right - index'

CThe base case condition should be 'in_left >= in_right' instead of 'in_left > in_right'

DThe root value should be taken from 'postorder[post_left]' instead of 'postorder[post_right]'

Step-by-Step Solution

Solution:

Step 1: Analyze base case
The base case should stop recursion when the segment is empty. Using 'in_left > in_right' correctly handles empty segments; changing to '>=' would incorrectly skip single-node segments.
Step 2: Check subtree sizes and indices
The calculation of left_tree_size and recursive calls are correct as given.
Final Answer:
Option C -> Option C
Quick Check:
Base case must handle empty segment properly [OK]

Quick Trick: Base case must handle empty segment correctly with '>' [OK]

Common Mistakes:

MISTAKES

Using '>=' instead of '>' in base case causing missed nodes
Miscalculating subtree sizes
Incorrect postorder index usage for root

Trap Explanation:

PITFALL

Base case with '>=' excludes single-node segments causing incomplete tree

Interviewer Note:

CONTEXT

Tests ability to identify subtle off-by-one errors in recursion base cases

Master "Construct Tree from Inorder and Postorder" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Tree: Depth-First Search Quizzes

In the following recursive function for building a binary tree from inorder and postorder traversals, which line contains a subtle bug that can cause incorrect tree construction or runtime errors?

Step 1: Analyze base case

Step 2: Check subtree sizes and indices

Final Answer:

Quick Check:

Want More Practice?