Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Google SWE coding round, one tree reconstruction problem and that was basically it. Pretty standard technical screen but the question has more edge cases than it looks.

Questions Asked (1)

Given the preorder and inorder traversals of a binary tree, reconstruct the original tree.

Algorithms & Data Structures

Author's notes

I knew the general idea going in but fumbled the index math when splitting the inorder array recursively.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use the first element of the preorder traversal as the root, then locate that root in the inorder traversal to split the tree into left and right subtrees. Recursively apply this process to reconstruct the entire tree, using a hash map to achieve O(n) time complexity.

Pro tip: Mention that using a hash map to store the indices of inorder elements reduces the time complexity from O(n^2) to O(n), and discuss how to handle edge cases like duplicate values or empty traversals.

1. Identify the root

The first element in the preorder traversal is always the root of the current subtree. This holds for the entire tree and recursively for each subtree.

2. Split inorder traversal

Find the root's index in the inorder traversal. Elements to the left belong to the left subtree, and elements to the right belong to the right subtree.

3. Determine subtree sizes

Calculate the number of nodes in the left and right subtrees based on the inorder split. Use these sizes to partition the preorder traversal accordingly.

4. Recursively build subtrees

Recursively apply the same process to the left and right subtrees using the partitioned preorder and inorder segments.

5. Optimize with hash map

Precompute a hash map mapping inorder values to their indices to achieve O(1) lookup for the root's position, reducing overall time complexity to O(n).

Key Points to Mention

Time and space complexity analysis: O(n) time with hash map, O(n) space for recursion and hash map.
Handling edge cases: empty traversals, single node, skewed trees, and duplicate values (if allowed).
The role of preorder (root first) and inorder (left-root-right) in determining the tree structure.
Recursive approach and how to pass indices to avoid copying arrays.
Alternative iterative approach using a stack, if asked for optimization.
Uniqueness of the tree given the traversals (assuming no duplicates).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.