algoadvance

Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal

Problem Statement

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.

• Example:
  • Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
  • Output:

        3
       / \
      9  20
        /  \
       15   7
    

Clarifying Questions

1. Can the given tree contain duplicate values?
   • No, the problem assumes that there are no duplicate values in the binary tree.
2. What should be returned if the input arrays are empty?
   • If the input arrays are empty, the function should return null (i.e., the tree is empty).
3. Is the length of both arrays guaranteed to be the same?
   • Yes, the lengths of both provided arrays preorder and inorder will be the same.

Strategy

1. Understand Preorder and Inorder Traversals:
   • In preorder traversal, the nodes are visited in this order: root -> left subtree -> right subtree.
   • In inorder traversal, the nodes are visited in this order: left subtree -> root -> right subtree.
2. Identify the root node:
   • The first element in the preorder array is the root of the tree.
3. Split the inorder array:
   • Find the index of the root node in the inorder array.
   • Elements to the left of this index in the inorder array represent the left subtree.
   • Elements to the right of this index represent the right subtree.
4. Recursive Approach:
   • Recursively construct left and right subtrees using the sliced parts of the preorder and inorder arrays.
   • Combine these subtrees to form the entire tree.

Code

Here’s the Java implementation of the solution:

import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int preorderIndex;
    private HashMap<Integer, Integer> inorderIndexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preorderIndex = 0;
        inorderIndexMap = new HashMap<>();
        
        // Build a hashmap to store value -> index relations
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }

        return buildTreeHelper(preorder, 0, inorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int inorderStart, int inorderEnd) {
        // Base case - no elements to construct the tree
        if (inorderStart > inorderEnd) {
            return null;
        }

        // The first element in preorder is the root node of the current subtree
        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);

        // Root splits inorder list into left and right subtrees
        int rootIndex = inorderIndexMap.get(rootVal);

        // Build left subtree
        root.left = buildTreeHelper(preorder, inorderStart, rootIndex - 1);

        // Build right subtree
        root.right = buildTreeHelper(preorder, rootIndex + 1, inorderEnd);

        return root;
    }
}

Time Complexity

• Time Complexity: O(n)
  • Building the inorderIndexMap takes O(n) time.
  • Each recursive call processes a node and splits the inorder array, resulting in O(n) operations.
• Space Complexity: O(n)
  • The space for the HashMap storing the inorder indices is O(n).
  • Recursive call stack can go up to O(n) in the case of a skewed tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?