Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonMicrosoftGoogleFacebook

Construct Tree from Preorder and Inorder

Choose your preparation mode4 modes available
</>
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
}
0/10
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
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}}}

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.

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}}}

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

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

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

t2_02edge
Input{"preorder":[42],"inorder":[42]}
Expected{"val":42,"left":null,"right":null}

Single node tree with root value 42 and no children.

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}

Tree with only left children forming a 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}}}}}

Tree with only right children forming a 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}}

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

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

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

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

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

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]}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
1. Consider the following iterative postorder traversal code to compute the maximum path sum in a binary tree. Given the tree below, what is the final value of max_sum after the function completes? Tree structure: ``` 1 / 2 3 ```
class TreeNode:
    def __init__(self, val=0, left=null, right=null):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    if not root:
        return 0
    max_sum = float('-inf')
    stack = []
    node = root
    last_visited = null
    gain_map = {}

    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek = stack[-1]
            if peek.right and last_visited != peek.right:
                node = peek.right
            else:
                left_gain = max(gain_map.get(peek.left, 0), 0)
                right_gain = max(gain_map.get(peek.right, 0), 0)
                current_path_sum = peek.val + left_gain + right_gain
                max_sum = max(max_sum, current_path_sum)
                gain_map[peek] = peek.val + max(left_gain, right_gain)
                last_visited = stack.pop()
    return max_sum
easy
A. 5
B. 4
C. 6
D. 3

Solution

  1. Step 1: Trace left subtree gain

    Node 2 has no children, so left_gain=0, right_gain=0, current_path_sum=2, max_sum updated to 2, gain_map[2]=2.
  2. Step 2: Trace root and right subtree

    Node 3 has no children, current_path_sum=3, max_sum updated to 3, gain_map[3]=3. For root 1, left_gain=2, right_gain=3, current_path_sum=1+2+3=6, max_sum updated to 6.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sum of path 2 -> 1 -> 3 is 6 [OK]
Hint: Sum path 2->1->3 yields max sum 6 [OK]
Common Mistakes:
  • Ignoring one child's gain leads to 5 or 4
  • Off-by-one in gain_map updates
  • Returning partial sums instead of max path sum
2. Suppose you want to perform inorder traversal on a binary tree where nodes can have parent pointers but no left or right child pointers. Which approach correctly produces the inorder sequence without recursion or extra stack?
hard
A. Use Morris traversal by creating threads on parent pointers instead of child pointers.
B. Use breadth-first search since parent pointers allow level order traversal.
C. Use recursive traversal ignoring parent pointers, which will fail due to missing child links.
D. Use iterative traversal with a pointer to the current node and track previously visited node to decide traversal direction.

Solution

  1. Step 1: Understand traversal constraints

    Without left/right child pointers, Morris traversal is not applicable since it relies on child links.
  2. Step 2: Use parent pointers to simulate traversal

    By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Tracking previous node enables correct traversal without extra space [OK]
Hint: Parent pointers + prev node tracking enable traversal [OK]
Common Mistakes:
  • Trying to create threads on parent pointers
  • Using recursion without child pointers
  • Confusing BFS with inorder traversal
3. Suppose the binary tree nodes can have negative values and you want to find the diameter defined as the longest path in terms of number of edges (ignoring node values). Which modification to the standard diameter algorithm is necessary to handle this variant correctly?
hard
A. No modification needed; the standard diameter algorithm based on heights works regardless of node values.
B. Modify the algorithm to sum node values along paths and find maximum sum path instead of longest path.
C. Change the height calculation to ignore negative nodes by treating them as null nodes.
D. Use breadth-first search to find the longest path instead of depth-first traversal.

Solution

  1. Step 1: Recognize diameter depends on path length (edges), not node values.

    Negative values do not affect height or path length calculations.
  2. Step 2: Confirm standard height-based diameter algorithm works unchanged.

    Heights and diameter calculations rely on structure, so no changes are needed.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Diameter depends on edges, not node values [OK]
Hint: Diameter is structural, unaffected by node values [OK]
Common Mistakes:
  • Confusing diameter with max sum path
  • Ignoring negative nodes incorrectly
  • Switching to BFS unnecessarily
4. Suppose the problem is modified so that you can rob the same node multiple times (i.e., nodes can be reused any number of times), but still cannot rob directly connected nodes simultaneously. Which modification to the algorithm is necessary to correctly solve this variant?
hard
A. Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse.
B. Use the same DFS with two-value return; no changes needed since adjacency constraints remain.
C. Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection.
D. Modify the DFS to allow revisiting nodes multiple times and use memoization keyed by node and robbing state.

Solution

  1. Step 1: Understand the reuse constraint

    Allowing multiple robberies per node breaks the tree structure assumption and simple one-time visit DFS.
  2. Step 2: Identify necessary algorithmic change

    We must track states including how many times a node is robbed and ensure adjacency constraints per robbery. Memoization keyed by node and robbing state prevents exponential recomputation.
  3. Step 3: Why other options fail

    Use the same DFS with two-value return; no changes needed since adjacency constraints remain. ignores reuse; Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection. is overcomplicated and unnecessary since the structure is still a tree; Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse. is vague and does not address adjacency constraints properly.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Memoization with extended state handles reuse and adjacency constraints [OK]
Hint: Reuse requires stateful memoization, not simple DFS [OK]
Common Mistakes:
  • Assuming original DFS suffices for reuse
  • Ignoring adjacency constraints when reusing nodes
5. Suppose the problem is modified so that paths can move both downwards and upwards (i.e., any connected path in the tree, not necessarily parent-to-child). Which of the following changes to the algorithm is necessary to correctly count all such paths?
hard
A. Convert the tree to an undirected graph and use DFS from every node with prefix sums, resetting counts after each start.
B. Use the brute force approach checking all paths from every node without prefix sums.
C. Use the same prefix sum DFS approach but run it twice: once from root down and once from leaves up.
D. Modify the prefix sum map to store sums for paths in both directions simultaneously during one DFS.

Solution

  1. Step 1: Understand path direction relaxation

    Allowing upward and downward moves means paths are any connected sequences, not just parent-to-child.
  2. Step 2: Model tree as undirected graph and run DFS from every node

    To count all paths, treat tree as undirected graph and run DFS from each node, using prefix sums and resetting counts to avoid cross-branch contamination.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Undirected DFS from every node with prefix sums counts all connected paths [OK]
Hint: Undirected graph DFS needed for arbitrary path directions [OK]
Common Mistakes:
  • Trying to reuse one-directional prefix sum DFS without modification
  • Assuming running DFS twice covers all paths
  • Trying to store both directions in one prefix sum map
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