Construct Tree from Inorder and Postorder

📋

Construct Tree from Inorder and Postorder

Edge cases:

</>

IDE

def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:public TreeNode buildTree(int[] inorder, int[] postorder)TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)function buildTree(inorder, postorder)

def buildTree(inorder, postorder):
    # Write your solution here
    pass

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    // Write your solution here
    return nullptr;
}

function buildTree(inorder, postorder) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Incorrect tree structure with wrong root or subtree nodesNot using last element of postorder as root or incorrect splitting of inorder array✅ Always select root as postorder[-1] and split inorder at root index to recurse on left and right subtrees

Wrong: Function crashes or returns non-null for empty input arraysMissing base case for empty arrays✅ Add base case: if not inorder or not postorder, return None

Wrong: Wrong tree shape for skewed treesIncorrect slicing of postorder or inorder arrays causing off-by-one errors✅ Ensure postorder slices correspond exactly to sizes of left and right inorder partitions

Wrong: Time limit exceeded on large inputsRepeated linear search for root index in inorder array causing O(n^2) complexity✅ Use a hashmap to store value to index mappings for inorder to achieve O(1) lookups

✓

Test Cases

Make sure your solution handles empty and single-node trees correctly before moving on.

Focus on correct subtree boundaries and avoid greedy root selection traps.

Optimize your root index lookup with a hashmap to handle large inputs efficiently.

t1_01basic

Input{"inorder":[9,3,15,20,7],"postorder":[9,15,7,20,3]}

Expected[3,9,20,null,null,15,7]

⏱ Performance - must finish in 2000ms

Root is 3 (last in postorder). In inorder, left subtree is [9], right subtree is [15,20,7]. Recursively build left and right subtrees.

💡 Recall that the last element in postorder is the root of the tree.

💡 Use the root value to split inorder into left and right subtrees and recurse.

💡 Build left subtree from inorder[:root_index] and postorder[:root_index], right subtree from inorder[root_index+1:] and postorder[root_index:-1].

Why it failed: Incorrect tree structure or values. Likely root not identified correctly or subtree boundaries miscalculated. Fix by ensuring root is last postorder element and splitting inorder correctly.

✓ Correctly identified root and recursively constructed left and right subtrees.

t1_02basic

Input{"inorder":[2,1,3],"postorder":[2,3,1]}

Expected[1,2,3]

⏱ Performance - must finish in 2000ms

Root is 1 (last in postorder). Left subtree inorder [2], right subtree inorder [3]. Construct left and right subtrees accordingly.

💡 Identify root as last element in postorder traversal.

💡 Split inorder array at root to find left and right subtree nodes.

💡 Recurse on left and right subtrees with corresponding postorder slices.

Why it failed: Wrong tree structure due to incorrect subtree slicing or root selection. Fix by correctly using root index in inorder to partition arrays.

✓ Correctly reconstructed tree with root 1 and children 2 and 3.

t2_01edge

Input{"inorder":[],"postorder":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty arrays represent an empty tree, so output is null.

💡 Check if input arrays are empty before processing.

💡 Return null or None immediately if inorder or postorder is empty.

💡 Base case: if not inorder or not postorder, return None.

Why it failed: Function crashes or returns non-null for empty input. Fix by adding base case to return None when arrays are empty.

✓ Correctly returns null for empty input arrays.

t2_02edge

Input{"inorder":[1],"postorder":[1]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node tree with root 1, no children.

💡 For single element arrays, root is that element and no subtrees exist.

💡 Base case: if length of inorder is 1, return node with that value.

💡 Ensure recursion handles single element arrays correctly without slicing errors.

Why it failed: Fails to return single node tree or crashes on single element input. Fix by handling base case of single element arrays properly.

✓ Correctly returns single node tree.

t2_03edge

Input{"inorder":[4,3,2,1],"postorder":[4,3,2,1]}

Expected[1,2,null,3,null,4]

⏱ Performance - must finish in 2000ms

Tree with only left children: root 1, left subtree 2, left subtree of 2 is 3, and so on.

💡 Inorder sorted ascending but postorder ends with root.

💡 Left skewed tree means all nodes are left children only.

💡 Check that recursion correctly builds left subtree and right subtree is null.

Why it failed: Incorrect tree shape, possibly treating left subtree as right or vice versa. Fix by correctly slicing inorder and postorder for left subtree only.

✓ Correctly constructs left skewed tree.

t2_04edge

Input{"inorder":[1,2,3,4],"postorder":[4,3,2,1]}

Expected[1,null,2,null,3,null,4]

⏱ Performance - must finish in 2000ms

Tree with only right children: root 1, right subtree 2, right subtree of 2 is 3, and so on.

💡 Right skewed tree means all nodes are right children only.

💡 Check that recursion correctly builds right subtree and left subtree is null.

💡 Ensure slicing of postorder matches inorder partitions exactly.

Why it failed: Incorrect tree shape due to wrong subtree slicing. Fix by correctly slicing inorder and postorder for right subtree only.

✓ Correctly constructs right skewed tree.

t3_01corner

Input{"inorder":[1,2,3,4,5],"postorder":[1,3,5,4,2]}

Expected[2,1,4,null,null,3,5]

⏱ Performance - must finish in 2000ms

Test to catch greedy approach that picks wrong root or subtree. Root is 2, left subtree [1], right subtree [3,4,5].

💡 Do not pick root as first or middle element; root is last in postorder.

💡 Use root to split inorder correctly, not greedily choosing largest or smallest.

💡 Ensure recursion respects root position in postorder and splits inorder accordingly.

Why it failed: Greedy root selection leads to wrong tree structure. Fix by always using last postorder element as root and splitting inorder accordingly.

✓ Correctly avoids greedy trap and builds proper tree.

t3_02corner

Input{"inorder":[1,2,3],"postorder":[3,2,1]}

Expected[1,null,2,null,3]

⏱ Performance - must finish in 2000ms

Right skewed tree to catch confusion between 0/1 constraints or subtree boundaries.

💡 Right skewed means all nodes have only right children.

💡 Check that left subtree is empty and right subtree is built correctly.

💡 Ensure slicing of postorder matches inorder partitions exactly.

Why it failed: Incorrect subtree boundaries cause wrong tree shape. Fix by carefully slicing postorder to match inorder partitions for left and right subtrees.

✓ Correctly constructs right skewed tree.

t3_03corner

Input{"inorder":[2,1,4,3,5],"postorder":[2,4,5,3,1]}

Expected[1,2,3,null,null,4,5]

⏱ Performance - must finish in 2000ms

Test off-by-one errors in slicing arrays for left and right subtrees.

💡 Check indices carefully when slicing inorder and postorder arrays.

💡 Ensure postorder slices exclude the last element (root) correctly.

💡 Verify that left subtree size matches inorder left partition size.

Why it failed: Off-by-one errors cause incorrect subtree sizes or missing nodes. Fix by adjusting slice indices to match subtree sizes exactly.

✓ Correctly handles array slicing without off-by-one errors.

t4_01performance

Input{"inorder":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"postorder":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, linear right skewed tree. O(n^2) brute force will time out; optimized O(n) needed.

💡 Brute force linear search for root index causes O(n^2) time.

💡 Use a hashmap to store inorder value to index for O(1) lookups.

💡 Implement recursion with hashmap to achieve O(n) time complexity.

Why it failed: TLE due to O(n^2) complexity from repeated linear searches. Fix by using hashmap for inorder indices to reduce to O(n).

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

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. What is the time complexity of the Morris inorder traversal algorithm on a binary tree with n nodes?

medium

A. O(n) because each edge is visited at most twice during threading and unthreading.

B. O(n \times h) where h is tree height due to repeated traversal of left subtrees.

C. O(n \log n) due to repeated searching for predecessors.

D. O(n^2) in worst case when tree is skewed and predecessor search is costly.

Solution

1. Step 1: Analyze predecessor visits

   Each node's left subtree is traversed to find the predecessor, which can take up to h steps where h is the height of the tree.

2. Step 2: Count total operations

   In skewed trees, this leads to O(n x h) time complexity due to repeated traversal of left subtrees.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case time complexity is O(n x h) [OK]

Hint: Predecessor search can take O(h) per node in skewed trees [OK]

Common Mistakes:

• Assuming predecessor search is O(1) per node
• Confusing threading effect with total complexity
• Ignoring skewed tree worst case

3. What is the time complexity of the optimal countNodes algorithm that uses binary search on the last level of a complete binary tree with n nodes?

medium

A. O(log n)

B. O(n)

C. O((log n)^2)

D. O(n log n)

Solution

1. Step 1: Analyze height and binary search

   Height h = O(log n). Binary search on last level does O(log n) steps.

2. Step 2: Combine existence checks

   Each existence check traverses height h = O(log n). Total time = O(log n) * O(log n) = O((log n)^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested log factors from height and binary search [OK]

Hint: Two nested log factors multiply to (log n)^2 [OK]

Common Mistakes:

• Confusing O(log n) with O((log n)^2)
• Assuming linear time due to traversal

4. The following code attempts to solve the House Robber III problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 5: rob_current calculation uses left[0] and right[0]

B. Line 7: Returning (rob_current, not_rob_current)

C. Line 6: not_rob_current uses max(left) + max(right)

D. Line 2: Base case returns (0, 0)

Solution

1. Step 1: Understand rob_current calculation

   rob_current should be node.val plus the not_rob values of left and right children, because robbing current node forbids robbing immediate children.

2. Step 2: Identify the bug

   Line 5 incorrectly adds left[0] and right[0] (rob values of children), violating adjacency constraint.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using rob values of children overcounts and breaks correctness [OK]

Hint: Rob current node + not_rob children, not rob children [OK]

Common Mistakes:

• Mixing rob and not_rob indices in tuple
• Forgetting adjacency constraints

5. 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