Construct Tree from Preorder and Inorder

📋

Construct Tree from Preorder and Inorder

Edge cases:

</>

IDE

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

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

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

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: Incorrect tree structure missing left or right subtree nodesIncorrect slicing of preorder or inorder arrays causing subtree sizes to mismatch✅ Slice preorder as preorder[1:1+root_index] for left subtree and preorder[1+root_index:] for right subtree using root index from inorder

Wrong: Function returns null for non-empty inputBase case incorrectly returns null without building nodes✅ Add base case to return null only if preorder or inorder arrays are empty, otherwise build TreeNode

Wrong: Time Limit Exceeded (TLE)Using array slicing and index() calls repeatedly causing O(n^2) complexity✅ Use a hashmap to store inorder value to index mapping and pass indices to recursion instead of slicing arrays

Wrong: Incorrect tree with swapped left and right childrenConfusing preorder and inorder traversal roles or mixing left and right subtree construction✅ Remember preorder root first, then left subtree, then right subtree; inorder left subtree, root, right subtree

Wrong: Function crashes or returns incorrect result on duplicate valuesInput violates uniqueness constraint causing ambiguous root index lookup✅ Validate input arrays for uniqueness before processing or document constraints clearly

✓

Test Cases

Handle base cases like empty arrays and single node trees to proceed.

Check your slicing logic carefully and validate input uniqueness.

Optimize your recursion by avoiding array slicing and using a hashmap.

t1_01basic

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

Expected{"val":3,"left":{"val":9,"left":null,"right":null},"right":{"val":20,"left":{"val":15,"left":null,"right":null},"right":{"val":7,"left":null,"right":null}}}

⏱ Performance - must finish in 2000ms

The first element in preorder is the root (3). In inorder, elements left of 3 (9) form the left subtree, elements right of 3 (15,20,7) form the right subtree. Recursively apply the same logic.

💡 Recall that preorder traversal visits root first, then left subtree, then right subtree.

💡 Use the root value from preorder to split the inorder array into left and right subtrees.

💡 Recursively build left and right subtrees using corresponding preorder and inorder slices.

Why it failed: Incorrect tree structure returned. Likely cause: not correctly splitting inorder array by root or incorrect preorder slicing. Fix by ensuring root index in inorder is found and preorder slices match left and right subtree sizes.

✓ Correct tree constructed matching preorder and inorder traversals.

t1_02basic

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

Expected{"val":1,"left":{"val":2,"left":{"val":4,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}},"right":{"val":3,"left":null,"right":{"val":6,"left":null,"right":null}}}

⏱ Performance - must finish in 2000ms

Root is 1 from preorder. Left subtree inorder is [4,2,5], right subtree inorder is [3,6]. Recursively build subtrees accordingly.

💡 Identify root from preorder and find its index in inorder to split left and right subtrees.

💡 Ensure preorder slices correspond to the size of left and right subtrees determined from inorder.

💡 Build left subtree with preorder[1:1+left_subtree_size] and inorder[:root_index], right subtree with remaining slices.

Why it failed: Wrong subtree sizes used when slicing preorder or inorder arrays. Fix by calculating left subtree size from inorder and slicing preorder accordingly.

✓ Tree correctly reconstructed with proper subtree divisions.

t2_01edge

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

Expectednull

⏱ Performance - must finish in 2000ms

Empty preorder and inorder arrays represent an empty tree, so return null.

💡 Check if preorder or inorder arrays are empty before processing.

💡 Return null immediately if either array is empty.

💡 This handles the base case of an empty tree.

Why it failed: Function does not handle empty input arrays and returns non-null. Fix by adding base case: if not preorder or not inorder, return null.

✓ Correctly returns null for empty input arrays.

t2_02edge

Input{"preorder":[42],"inorder":[42]}

Expected{"val":42,"left":null,"right":null}

⏱ Performance - must finish in 2000ms

Single node tree with root value 42 and no children.

💡 For single element arrays, root is that element with no children.

💡 Ensure base case returns a node with val and null children.

💡 Avoid slicing beyond array bounds for single element.

Why it failed: Fails to return a single node tree correctly, possibly returning null or incorrect children. Fix by handling single element base case properly.

✓ Correctly constructs single node tree.

t2_03edge

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

Expected{"val":5,"left":{"val":4,"left":{"val":3,"left":{"val":2,"left":{"val":1,"left":null,"right":null},"right":null},"right":null},"right":null},"right":null}

⏱ Performance - must finish in 2000ms

Tree with only left children forming a linear left skewed tree.

💡 Check that your code handles skewed trees where all nodes are left children.

💡 Verify preorder and inorder slicing correctly reflects left subtree sizes.

💡 Avoid assumptions that right subtree always exists.

Why it failed: Incorrect handling of skewed left subtree, possibly creating right children or missing nodes. Fix by correctly slicing arrays and building left subtree recursively.

✓ Correctly constructs linear left skewed tree.

t2_04edge

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

Expected{"val":1,"left":null,"right":{"val":2,"left":null,"right":{"val":3,"left":null,"right":{"val":4,"left":null,"right":{"val":5,"left":null,"right":null}}}}}

⏱ Performance - must finish in 2000ms

Tree with only right children forming a linear right skewed tree.

💡 Check that your code handles skewed trees where all nodes are right children.

💡 Verify preorder and inorder slicing correctly reflects right subtree sizes.

💡 Avoid assumptions that left subtree always exists.

Why it failed: Incorrect handling of skewed right subtree, possibly creating left children or missing nodes. Fix by correctly slicing arrays and building right subtree recursively.

✓ Correctly constructs linear right skewed tree.

t3_01corner

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

Expected{"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}

⏱ Performance - must finish in 2000ms

Small balanced tree to catch off-by-one errors in slicing preorder array.

💡 Verify that preorder slicing for left subtree is exactly root_index elements after root.

💡 Check that right subtree preorder slice starts immediately after left subtree slice.

💡 Off-by-one errors cause missing or extra nodes in subtrees.

Why it failed: Off-by-one error in preorder slicing causes incorrect subtree sizes. Fix by slicing preorder as preorder[1:1+root_index] for left and preorder[1+root_index:] for right.

✓ Correct preorder slicing produces correct tree.

t3_02corner

Input{"preorder":[1,2,2],"inorder":[2,1,2]}

Expectednull

⏱ Performance - must finish in 2000ms

Invalid input with duplicate values violates uniqueness constraint; function should handle or reject gracefully.

💡 Problem states preorder and inorder have unique values; check input validity.

💡 If duplicates exist, index lookup for root in inorder is ambiguous.

💡 Consider returning null or raising error for invalid input.

Why it failed: Function does not handle duplicate values and returns incorrect tree or crashes. Fix by validating input uniqueness before processing.

✓ Function correctly handles or rejects invalid input with duplicates.

t3_03corner

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

Expectednull

⏱ Performance - must finish in 2000ms

Input where inorder does not match preorder tree structure, testing validation of input consistency.

💡 Check if inorder array matches preorder tree structure.

💡 If root index in inorder is not found or subtree sizes mismatch, input is invalid.

💡 Return null or error for inconsistent input.

Why it failed: Function builds incorrect tree or crashes on inconsistent input. Fix by validating that inorder and preorder arrays represent the same tree.

✓ Function correctly detects inconsistent input and returns null.

t4_01performance

Input{"preorder":[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],"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]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, linear right skewed tree input. Optimized O(n) solution must complete within 2 seconds.

💡 Brute force slicing leads to O(n^2) time; use hashmap to store inorder indices.

💡 Avoid repeated calls to index() by precomputing a map from value to index.

💡 Use recursion with indices instead of slicing arrays.

Why it failed: Brute force recursion with slicing causes TLE due to O(n^2) complexity. Fix by using hashmap for inorder indices and passing indices instead of slicing.

✓ Solution runs in O(n) time using hashmap and index boundaries.

Practice

1. Consider the following code snippet implementing the optimal countNodes function for a complete binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final return value of countNodes(root)?

easy

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Calculate tree height

   Height h = 3 (nodes 1 -> 2 -> 4).

2. Step 2: Binary search on last level nodes

   Last level has indices 0 to 3. Check existence: - idx=0 exists (node 4) - idx=1 does not exist So left ends at 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]

Hint: Count = perfect nodes + last level nodes found [OK]

Common Mistakes:

• Off-by-one in binary search bounds
• Miscounting last level nodes

2. You are given a binary tree where each node contains a non-negative integer value. You want to maximize the sum of values you can collect by selecting nodes such that no two directly connected nodes (parent-child) are both selected. Which approach guarantees an optimal solution for this problem?

easy

A. Use a greedy algorithm that always picks the node with the highest value first.

B. Use a depth-first search with dynamic programming that returns two values per node: max if robbing it and max if not robbing it.

C. Use a breadth-first search to select nodes level by level, picking the maximum values at alternate levels.

D. Use a brute force recursion that tries all subsets of nodes without any memoization.

Solution

1. Step 1: Understand the problem constraints

   The problem requires selecting nodes in a tree such that no parent and child are both selected, maximizing the sum of selected nodes.

2. Step 2: Identify the suitable algorithmic pattern

   A greedy or BFS level-based approach fails because the tree structure and adjacency constraints are complex. Brute force is correct but inefficient. The optimal solution uses DFS with DP returning two values per node: max if robbing it and max if not robbing it, ensuring all subproblems are solved optimally.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DFS with two-value DP handles adjacency constraints correctly [OK]

Hint: Tree + no adjacent nodes -> DFS with two-value DP [OK]

Common Mistakes:

• Assuming greedy or level-based selection works
• Trying brute force without memoization

3. Consider the following iterative DFS code snippet for counting paths with sum equal to targetSum in a binary tree. Given the tree with root value 1, left child 2, right child 3, and targetSum = 3, what is the final value of result after the loop finishes?

class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}
        result = 0
        stack = [(root, 0, False)]  # node, current_sum, visited_children

        while stack:
            node, current_sum, visited = stack.pop()
            if node is None:
                continue
            if not visited:
                current_sum += node.val
                result += prefix_counts.get(current_sum - targetSum, 0)
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
                stack.append((node, current_sum, True))  # Mark node as visited
                stack.append((node.right, current_sum, False))
                stack.append((node.left, current_sum, False))
            else:
                prefix_counts[current_sum] -= 1

        return result

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Trace initial stack and prefix_counts

   Start with stack=[(1,0,False)], prefix_counts={0:1}, result=0.

2. Step 2: Process nodes and update result

   Paths summing to 3 are: (1->2) and (3) alone, total 2 paths counted.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two valid paths found matching target sum [OK]

Hint: Count paths by prefix sums during DFS traversal [OK]

Common Mistakes:

• Missing the single node path (3)
• Double counting paths due to prefix_counts not decremented
• Off-by-one in updating result

4. You need to convert a binary tree into a string and then reconstruct the exact same tree from that string. Which approach guarantees that the tree structure, including null children, is preserved and can be reconstructed efficiently?

easy

A. Use level order traversal (BFS) including null markers for missing children, then deserialize by reading nodes level by level.

B. Use a greedy traversal that records only node values without null markers, then reconstruct by inserting nodes in order.

C. Use dynamic programming to store subtree encodings and reconstruct from stored subtrees.

D. Use inorder traversal without null markers and reconstruct by assuming a balanced tree.

Solution

1. Step 1: Understand the need for null markers

   Without null markers, the tree structure cannot be uniquely reconstructed because missing children are ambiguous.

2. Step 2: Recognize BFS with null markers preserves structure

   Level order traversal with null markers records nodes level by level, capturing the exact shape of the tree, enabling correct deserialization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Level order with null markers uniquely encodes tree structure [OK]

Hint: Null markers are essential to preserve tree shape [OK]

Common Mistakes:

• Ignoring null markers leads to ambiguous deserialization
• Assuming inorder traversal alone can reconstruct arbitrary trees
• Using greedy or DP approaches that don't preserve structure

5. Suppose the Path Sum problem is modified so that node values can be negative, and you want to find if any root-to-leaf path sums exactly to targetSum. Which of the following changes to the DFS approach is necessary to handle this correctly?

hard

A. Precompute all path sums and store them in a hash set for O(1) lookup

B. Add memoization to avoid revisiting nodes with the same current sum

C. Use BFS instead of DFS to guarantee shortest path sum

D. Remove early stopping because negative values can invalidate pruning assumptions

Solution

1. Step 1: Understand impact of negative values

   Negative values mean partial sums can decrease later, so pruning based on current sum is unsafe.

2. Step 2: Adjust algorithm accordingly

   Early stopping based on partial sums must be removed to avoid missing valid paths.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Negative values break pruning assumptions, so early stopping must be disabled [OK]

Hint: Negative values invalidate pruning, so no early stopping [OK]

Common Mistakes:

• Assuming early stopping always works
• Switching to BFS unnecessarily