LeetCode - Construct Binary Tree from Preorder and Inorder Traversal | Darren's Blog

Given preorder and inorder traversal of a tree, construct the binary tree

 public TreeNode buildTree(int[] preorder, int[] inorder) {

        if (preorder == null || inorder == null ||

                preorder.length != inorder.length || preorder.length == 0)

            return null;

        return recursiveBuildTree(preorder, 0, inorder, 0, preorder.length);

    }

    /**

     * Recursively build binary tree from preorder traversal and inorder traversal with given begining

     * indices of beginning nodes and effective number of nodes

     * @param preorder preorder traversal

     * @param preBegin index of the beginning node in the preorder traversal

     * @param inorder inorder traversal

     * @param inBegin index of the begining node in the inorder traversal

     * @param len number of nodes for both traversal

     * @return

     */

    private TreeNode recursiveBuildTree(int[] preorder, int preBegin, int[] inorder, int inBegin, int len) {

        assert preBegin+len <= preorder.length;

        assert inBegin+len <= inorder.length;

        if (len <= 0)       // Empty tree

            return null;

        // The beginning node in the preorder traversal is the root

        TreeNode root = new TreeNode(preorder[preBegin]);

        // Find the position of the root in the inorder traversal so as to decide the number of nodes

        // in its left subtree

        int leftTreeLen = 0;

        for(; leftTreeLen < len && inorder[inBegin+leftTreeLen] != root.val; leftTreeLen++);

        // Recursively build its left subtree and right subtree; note the change in preBegin, inBegin, and len

        TreeNode left = recursiveBuildTree(preorder, preBegin+1, inorder, inBegin, leftTreeLen);

        TreeNode right = recursiveBuildTree(preorder, preBegin+leftTreeLen+1, inorder, inBegin+leftTreeLen+1,

                len-leftTreeLen-1);

        // Link the left and right subtrees with the root

        root.left = left;

        root.right = right;

        return root;

    }

The running time T(n) satisfies the following relation:

T(n)=T(l)+T(n−l−1)+O(n).

When the tree is quite balanced, the time complexity is O(n) . But in case where the tree is very unbalanced (e.g. each node except the root is the right/left child of its parent), the time complexity grows up to O(n2) 
Read full article from LeetCode - Construct Binary Tree from Preorder and Inorder Traversal | Darren's Blog