Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonMicrosoftGoogle

Construct Tree from Inorder and Postorder

Choose your preparation mode4 modes available
</>
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
}
0/10
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
t1_01basic
Input{"inorder":[9,3,15,20,7],"postorder":[9,15,7,20,3]}
Expected[3,9,20,null,null,15,7]

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

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

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

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

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

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

Single node tree with root 1, no children.

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

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

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

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

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

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

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

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

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

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

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

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

Practice

(1/5)
1. Given the following code for the optimal camera placement, what is the final number of cameras placed for the tree with root node 0, left child 1, and right child 2 (both children are leaves)?
easy
A. 2
B. 0
C. 3
D. 1

Solution

  1. Step 1: Trace dfs on leaf nodes 1 and 2

    Leaves return NOT_COVERED (0) because their children are null and return COVERED_NO_CAM (1). So dfs(1) and dfs(2) return NOT_COVERED.
  2. Step 2: At root node 0, left or right child is NOT_COVERED, so place a camera here

    Increment cameras to 1 and return HAS_CAM (2). The root is covered, so no extra camera needed.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    One camera at root covers all nodes [OK]
Hint: Leaves uncovered -> camera at parent -> minimal cameras [OK]
Common Mistakes:
  • Counting cameras on leaves instead of parent
  • Forgetting to add camera at root if uncovered
  • Misinterpreting coverage states
2. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?
easy
A. Postorder traversal using two stacks
B. Level-order traversal using a queue
C. Morris preorder traversal using threaded binary tree
D. Inorder traversal using recursion

Solution

  1. Step 1: Understand traversal order requirement

    The problem requires visiting root before left and right subtrees, which is preorder traversal.
  2. Step 2: Identify approach with no extra space

    Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Preorder visits root first; Morris traversal achieves this with O(1) space [OK]
Hint: Preorder visits root before children [OK]
Common Mistakes:
  • Confusing inorder or postorder with preorder traversal
  • Assuming recursion is always needed
  • Using level-order which visits nodes by depth
3. What is the time complexity of the optimal DFS with two-value return solution for the House Robber III problem on a tree with n nodes?
medium
A. O(n^2) due to checking grandchildren nodes explicitly
B. O(n) but with extra O(n) space for memoization arrays
C. O(n) because each node is visited once in DFS
D. O(n log n) because of recursive calls and combining results

Solution

  1. Step 1: Identify DFS traversal cost

    The algorithm visits each node exactly once in a postorder DFS traversal.
  2. Step 2: Analyze operations per node

    At each node, constant time operations are done: combining left and right child results, no repeated work.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Linear traversal of n nodes -> O(n) time [OK]
Hint: DFS visits each node once, no repeated subproblems [OK]
Common Mistakes:
  • Assuming O(n^2) due to grandchildren checks
  • Confusing recursion stack space with time complexity
4. Suppose the problem is modified so that the path can reuse nodes multiple times (i.e., cycles allowed), and node values can be negative. Which of the following approaches correctly adapts the maximum path sum algorithm to handle this variant?
hard
A. Use the same postorder traversal with global max tracking, ignoring negative gains as before.
B. Detect cycles and use dynamic programming with memoization to avoid infinite loops, allowing repeated nodes in paths.
C. Convert the tree to a graph and run Bellman-Ford algorithm to find the maximum sum path allowing cycles.
D. Use depth-first search with pruning to explore all paths, but limit path length to avoid infinite loops.

Solution

  1. Step 1: Understand the impact of allowing node reuse

    Allowing cycles means paths can revisit nodes infinitely, so naive DFS or postorder traversal fails due to infinite loops.
  2. Step 2: Identify correct approach

    Dynamic programming with cycle detection and memoization prevents infinite recursion and correctly computes max sums with repeated nodes.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Memoization with cycle detection handles repeated nodes safely [OK]
Hint: Cycle detection and memoization needed for repeated nodes [OK]
Common Mistakes:
  • Using same postorder traversal causes infinite loops
  • Bellman-Ford is for shortest paths, not max sums with negative cycles
  • DFS without cycle checks leads to infinite recursion
5. 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
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