Construct a Binary Tree from Preorder and Inorder
Updated
Problem statement
You are given preorder and inorder, the preorder and inorder traversals of the same binary tree. Every node value is distinct. Reconstruct and return that tree.
- Preorder visits a node, then its left subtree, then its right subtree.
- Inorder visits the left subtree, then the node, then its right subtree.
The two arrays have the same length, contain the same values, and are guaranteed to describe a valid tree. An empty pair describes an empty tree. Do not assume that node values follow binary-search-tree ordering.
The examples display the returned tree in level order. A null marks a missing child; trailing missing entries are omitted.
Function
buildTree(preorder: int[], inorder: int[]) → TreeNodeExamples
Example 1
preorder = [3,9,20,15,7]inorder = [9,3,15,20,7]return = [3,9,20,null,null,15,7]Root 3 has left child 9 and right child 20, whose children are 15 and 7.
Example 2
preorder = [-1]inorder = [-1]return = [-1]The only value is both the root and a leaf.
Example 3
preorder = []inorder = []return = []Both traversals are empty, so return an empty tree.
Constraints
0 <= preorder.length == inorder.length <= 1000.- Every node value is an integer from
-10^9to10^9, inclusive. - Node values are distinct, and the traversals are valid for the same binary tree.
More eBay interview questions
- Meeting Rooms IIPHONE SCREEN · Seen Oct 2026
- Maximum Size Subarray Sum Equals KPHONE SCREEN · Seen Sep 2026
- Longest Palindromic SubstringPHONE SCREEN · Seen Aug 2026
- K Smallest Elements from Sorted ArraysPHONE SCREEN · Seen Jul 2026
- Single-Pass Search in a Rotated Sorted ArrayPHONE SCREEN · Seen Jul 2026
- Xiangqi Horse ReachabilityPHONE SCREEN · Seen Jul 2026
- Count Staircases with Strictly Increasing StepsONSITE INTERVIEW · Seen Oct 2026
- Hierarchical Permission CheckONSITE INTERVIEW · Seen Oct 2026
- Matrix MultiplicationONSITE INTERVIEW · Seen Oct 2026
- N-Queens Solution CountONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Build a Tree from Preorder and Inorder TraversalsBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Construct a Tree from Level-Order and Inorder TraversalsAmazon · PHONE SCREEN
- Build a Tree from Preorder and Inorder TraversalsStackAdapt · ONSITE INTERVIEWStackAdapt interview questions
- Construct a Tree from Level-Order and Inorder TraversalsSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Lowest Common Ancestor in an N-ary TreeGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Tree Selection and VisibilityJane Street · PHONE SCREENJane Street interview questions
- Account Roles With Parent-User InheritanceStripe · PHONE SCREENStripe interview questions
- Worst-Performing Ads by CTR in a Campaign TreeUber · PHONE SCREENUber interview questions