LeetCode medium: Construct Binary Tree from Preorder and Inorder Traversal

When we are given Inorder traversal of nodes in a tree, along with 1 other traversal, either preorder or postorder,  we can derive the original tree structure from the provided information.

I have solved the following LeetCode problem with the same idea in mind:

Problem #105: LeetCode medium: Construct Binary Tree from Preorder and Inorder Traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder.length == 0 || preorder.length==0)
            return null;
        TreeNode root = treeFromInorderPreorder(inorder, 0, inorder.length-1, preorder, 0, preorder.length-1);
        return root;
    }
    
    private TreeNode treeFromInorderPreorder(int[] inorder, int inStart, int inEnd, int[] preorder, int preStart, int preEnd) {
        
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        
        int inRootIdx = inStart;
        for (int i=inStart; i<=inEnd; i++) {
            if (inorder[i]==rootVal) {
                inRootIdx = i;
                break;
            }
        }
        // assert(inRootIdx != -1);
        int nodesInLeftSubtree = inRootIdx - inStart;
        if (nodesInLeftSubtree == 0) {
            root.left = null;
        } else {
        root.left = treeFromInorderPreorder(inorder, inStart, inRootIdx-1, preorder, preStart+1, preStart+1+nodesInLeftSubtree);
        }
        
        int nodesInRightSubtree = inEnd - inRootIdx;
        if (nodesInRightSubtree == 0) {
            root.right = null;
        } else {
        root.right = treeFromInorderPreorder(inorder, inRootIdx+1, inEnd, preorder, preStart+nodesInLeftSubtree+1, preEnd);
        }
        
        return root;
    }
}

In the similar vein, consider:

Problem #106: Construct Binary Tree from Inorder and Postorder Traversal

The bounds for parameters with which to make recursive calls can be slightly tricky to understand so one needs to be careful with those.

Besides that, as always, let me know in comments if you find these solutions helpful or have ideas for improvement.

Toodles!...