Skip to content
AI360Xpert
Back to Trees
Medium

Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return the binary tree.

Examples

Input:preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output:[3,9,20,null,null,15,7]
Input:preorder = [-1], inorder = [-1]
Output:[-1]

Constraints

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values.
  • Each value of inorder also appears in preorder.
  • preorder is guaranteed to be the preorder traversal of the tree.
  • inorder is guaranteed to be the inorder traversal of the tree.

Approach

The first element in `preorder` is always the root. We find this root value in `inorder`. Everything to the left of it in `inorder` belongs to the left subtree, and everything to the right belongs to the right subtree. We can recursively build the tree by passing sliced arrays.

Complexity Analysis

Time Complexity
O(n^2)
Space Complexity
O(n^2)

Finding the index in inorder array takes O(n), and array slicing takes O(n), leading to O(n^2) overall time.

Solution.java
class Solution {    public TreeNode buildTree(int[] preorder, int[] inorder) {        if (preorder.length == 0 || inorder.length == 0) return null;                TreeNode root = new TreeNode(preorder[0]);        int mid = -1;        for (int i = 0; i < inorder.length; i++) {            if (inorder[i] == preorder[0]) {                mid = i;                break;            }        }                int[] leftPre = Arrays.copyOfRange(preorder, 1, mid + 1);        int[] leftIn = Arrays.copyOfRange(inorder, 0, mid);        root.left = buildTree(leftPre, leftIn);                int[] rightPre = Arrays.copyOfRange(preorder, mid + 1, preorder.length);        int[] rightIn = Arrays.copyOfRange(inorder, mid + 1, inorder.length);        root.right = buildTree(rightPre, rightIn);                return root;    }}