Construct Binary Tree from Preorder and Inorder Traversal

• If the preorder array is empty, return null.
• The first element of the preorder array, preorder[0], is the root of the tree. Create a TreeNode for this root.
• Find the index, mid, of the root's value in the inorder array. This is a linear scan.
• The elements to the left of mid in the inorder array form the left subtree. The elements to the right form the right subtree.
• The number of nodes in the left subtree is mid.
• Create new subarrays for the left and right subtrees:
  • left_inorder: inorder from index 0 to mid - 1.
  • right_inorder: inorder from index mid + 1 to the end.
  • left_preorder: preorder from index 1 to mid.
  • right_preorder: preorder from index mid + 1 to the end.
• Recursively call the function to build the left child: root.left = buildTree(left_preorder, left_inorder).
• Recursively call the function to build the right child: root.right = buildTree(right_preorder, right_inorder).
• Return the root node.

The core idea is to use recursion. The base case for the recursion is when the input arrays are empty, in which case we return null.

In each recursive step:

1. Pick the first element from the preorder array. This is the root of the current subtree.
2. Create a new TreeNode with this value.
3. Search for this root's value in the inorder array. Let's say its index is k.
4. All elements in the inorder array to the left of k (from index 0 to k-1) belong to the left subtree.
5. All elements in the inorder array to the right of k (from index k+1 to the end) belong to the right subtree.
6. The number of elements in the left subtree is k.
7. The next k elements in the preorder array (after the root) belong to the left subtree's preorder traversal. The rest belong to the right subtree's preorder traversal.
8. Create new subarrays for the left and right subtrees' traversals (left_inorder, right_inorder, left_preorder, right_preorder).
9. Recursively call the function to build the left and right children.

This process is simple to understand but inefficient due to the repeated creation of new arrays and linear scanning in each recursive call.

1import java.util.Arrays;2 3/**4 * Definition for a binary tree node.5 * public class TreeNode {6 *     int val;7 *     TreeNode left;8 *     TreeNode right;9 *     TreeNode() {}10 *     TreeNode(int val) { this.val = val; }11 *     TreeNode(int val, TreeNode left, TreeNode right) {12 *         this.val = val;13 *         this.left = left;14 *         this.right = right;15 *     }16 * }17 */18class Solution {19    public TreeNode buildTree(int[] preorder, int[] inorder) {20        if (preorder == null || preorder.length == 0) {21            return null;22        }23 24        // The first element of preorder is the root25        TreeNode root = new TreeNode(preorder[0]);26 27        // Find the root in the inorder array28        int mid = -1;29        for (int i = 0; i < inorder.length; i++) {30            if (inorder[i] == root.val) {31                mid = i;32                break;33            }34        }35 36        // Create subarrays for left and right subtrees37        int[] leftInorder = Arrays.copyOfRange(inorder, 0, mid);38        int[] rightInorder = Arrays.copyOfRange(inorder, mid + 1, inorder.length);39        int[] leftPreorder = Arrays.copyOfRange(preorder, 1, mid + 1);40        int[] rightPreorder = Arrays.copyOfRange(preorder, mid + 1, preorder.length);41 42        // Recursively build the left and right subtrees43        root.left = buildTree(leftPreorder, leftInorder);44        root.right = buildTree(rightPreorder, rightInorder);45 46        return root;47    }48}

• Initialize a global preorderIndex = 0 to track the current root in the preorder array.
• Call a recursive helper function build(inStart, inEnd) with initial bounds 0 and inorder.length - 1.
• Inside build(inStart, inEnd):
  • If inStart > inEnd, return null (base case).
  • Get the current root's value: rootVal = preorder[preorderIndex], and then increment preorderIndex.
  • Create a new TreeNode for the root.
  • Linearly scan the inorder array from inStart to inEnd to find the index inRootIndex of rootVal.
  • The left child is built by the recursive call build(inStart, inRootIndex - 1).
  • The right child is built by the recursive call build(inRootIndex + 1, inEnd).
  • Return the created root node.

We define a recursive helper function, say build(inStart, inEnd), which constructs a tree from preorder and a specific segment of inorder defined by inStart and inEnd.

A global or class-level variable, preorderIndex, is used to keep track of the current root in the preorder array. It's initialized to 0 and incremented each time a node is processed.

The algorithm for the helper function build(inStart, inEnd) is as follows:

1. Base case: If inStart > inEnd, it means the current subarray is empty, so return null.
2. Get the current root's value from preorder[preorderIndex] and increment preorderIndex.
3. Create a new TreeNode with this value.
4. Find the index of this root's value within the current inorder segment (inorder[inStart...inEnd]). This search is a linear scan.
5. Recursively call build for the left and right subtrees using the calculated boundaries.

This approach eliminates the space and time overhead of array copying, but the time complexity is still dominated by the linear search in each step.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode(int val) { this.val = val; }8 * }9 */10class Solution {11    int preorderIndex;12    int[] preorder;13    int[] inorder;14 15    public TreeNode buildTree(int[] preorder, int[] inorder) {16        this.preorder = preorder;17        this.inorder = inorder;18        this.preorderIndex = 0;19        return build(0, inorder.length - 1);20    }21 22    private TreeNode build(int inStart, int inEnd) {23        // Base case24        if (inStart > inEnd) {25            return null;26        }27 28        // Get current root from preorder and advance index29        int rootVal = preorder[preorderIndex++];30        TreeNode root = new TreeNode(rootVal);31 32        // Find root's index in the current inorder segment33        int inRootIndex = -1;34        for (int i = inStart; i <= inEnd; i++) {35            if (inorder[i] == rootVal) {36                inRootIndex = i;37                break;38            }39        }40 41        // Recursively build left and right subtrees42        // Important: Build left subtree first because preorderIndex is advanced sequentially43        root.left = build(inStart, inRootIndex - 1);44        root.right = build(inRootIndex + 1, inEnd);45 46        return root;47    }48}

• Create a HashMap<Integer, Integer> called inorderMap to store (value, index) pairs from the inorder array. This takes O(N) time.
• Initialize a global preorderIndex = 0.
• Call a recursive helper build(inStart, inEnd) with initial bounds 0 and inorder.length - 1.
• Inside build(inStart, inEnd):
  • If inStart > inEnd, return null.
  • Get rootVal = preorder[preorderIndex] and increment preorderIndex.
  • Create a root node with rootVal.
  • Get the root's index inRootIndex from the inorderMap in O(1) time: inRootIndex = inorderMap.get(rootVal).
  • Set root.left = build(inStart, inRootIndex - 1).
  • Set root.right = build(inRootIndex + 1, inEnd).
  • Return root.

The overall recursive structure is the same as the previous approach, using indices to define subarrays. The key improvement is the elimination of the linear search.

The algorithm is as follows:

1. First, create a HashMap to store the indices of elements in the inorder array. This takes O(N) time.
2. Initialize a global or class-level variable, preorderIndex, to 0.
3. Call a recursive helper function, build(inStart, inEnd), with the initial boundaries of the inorder array.
4. Inside the helper function, get the current root from preorder, create the node, and then use the HashMap to find its position in the inorder segment in O(1) time.
5. Recursively build the left and right subtrees.

By replacing the O(N) search with an O(1) lookup, the work done at each node becomes constant, leading to an overall linear time complexity.

1import java.util.HashMap;2import java.util.Map;3 4/**5 * Definition for a binary tree node.6 * public class TreeNode {7 *     int val;8 *     TreeNode left;9 *     TreeNode right;10 *     TreeNode(int val) { this.val = val; }11 * }12 */13class Solution {14    int preorderIndex;15    Map<Integer, Integer> inorderMap;16    int[] preorder;17 18    public TreeNode buildTree(int[] preorder, int[] inorder) {19        this.preorder = preorder;20        this.preorderIndex = 0;21        // Build a hashmap to store value -> index relations22        this.inorderMap = new HashMap<>();23        for (int i = 0; i < inorder.length; i++) {24            inorderMap.put(inorder[i], i);25        }26        return build(0, inorder.length - 1);27    }28 29    private TreeNode build(int inStart, int inEnd) {30        // Base case31        if (inStart > inEnd) {32            return null;33        }34 35        // Get current root from preorder and advance index36        int rootVal = preorder[preorderIndex++];37        TreeNode root = new TreeNode(rootVal);38 39        // Find root's index in inorder using the map (O(1) lookup)40        int inRootIndex = inorderMap.get(rootVal);41 42        // Recursively build left and right subtrees43        // Important: Build left subtree first because preorderIndex is advanced sequentially44        root.left = build(inStart, inRootIndex - 1);45        root.right = build(inRootIndex + 1, inEnd);46 47        return root;48    }49}