FastPrepRebuild a Binary Tree From Two Walks
Problems/Rebuild a Binary Tree From Two Walks

Rebuild a Binary Tree From Two Walks

Adobe logoAdobe● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: This problem asks to rebuild a binary tree with distinct values from two of its walks, preorder and inorder, and return the root. An Adobe CS-1 report mentions it as a first-round question that replaced an earlier one; only the approach was discussed, and the report gives no limits or examples.

Our choices: all node values are different (so the tree is unique), there are at most 800 nodes with values from -10^4 to 10^4, the answer is the root of the rebuilt tree, and the examples are new.

The judged task matches the report at about 80%.

A binary tree has different values in all its nodes. You are given two walks of it:

  • preorder: visit a node, then its left subtree, then its right subtree.
  • inorder: visit the left subtree, then the node, then the right subtree.

Rebuild the tree and return its root. Because all values are different, exactly one tree fits both walks.

Function

buildTree(preorder: int[], inorder: int[]) → TreeNode

Examples

Example 1

preorder = [5,9,2,7,4]inorder = [2,9,5,4,7]return = [5,9,7,2,null,4]

Preorder starts with the root, 5. In the inorder list, 2 and 9 come before 5, so they form the left subtree; 4 and 7 come after, so they form the right subtree. The left part of preorder is [9, 2]: 9 is its root and 2 its left child. The right part is [7, 4]: 7 is its root and 4 its left child.

Example 2

preorder = [4,6]inorder = [6,4]return = [4,6]

4 is the root. In inorder, 6 comes before 4, so 6 is in the left subtree: it is the left child of 4.

Example 3

preorder = [1,2,3]inorder = [1,2,3]return = [1,null,2,null,3]

Each root comes first in its part of the inorder list, so no node has a left subtree; each next preorder value is the right child of the one before, a chain to the right.

Constraints

  • 1 <= preorder.length <= 800 and inorder.length == preorder.length
  • -10^4 <= preorder[i], inorder[i] <= 10^4
  • All values are different, and inorder holds the same values as preorder.
  • The two lists are the preorder and inorder walks of one binary tree.

More Adobe problems

  • Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
  • All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
  • Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
All Adobe interview questionsSee Adobe hiring insights
Saved
public TreeNode buildTree(int[] preorder, int[] inorder) {
    // Write your code here.
}
Checking account…