1
\$\begingroup\$

I want you to pick my code apart and give me some feedback on how I could make it better or simpler. For a full tree (all nodes with 0 or 2 children) it works deterministically:

public class Construct {

    private TreeNode root;

    private static class TreeNode {
        TreeNode left;
        TreeNode right;
        int item;

        public TreeNode(TreeNode left, TreeNode right, int item) {
            this.left = left;
            this.right = right;
            this.item = item;
        }
    }

    public void treeFromPreOrderAndInorder(int[] pre, int[] inorder) {
        if (pre == null || inorder == null) {
            throw new IllegalArgumentException("Your tree is not accurate");
        }
        if (pre.length != inorder.length) {
            throw new IllegalArgumentException("Your tree is not accurate");
        }
        // should this be overloaded + testing.
        root =  treeFromPreOrderAndInorder(pre, 0, inorder, 0, inorder.length - 1); 
    }

    /**
     * Private functions are not overloaded.
     * Check binary0.
     */
    private TreeNode treeFromPreOrderAndInorder(int[] pre, int pos, int[] inorder, int lb, int hb) {
        if (lb > hb) return null;

        // step 1: fetch parent
        int parent = pre[pos];
        // step 2: fetch position
        int parentPosInorder;
        for (parentPosInorder = lb; parentPosInorder <= hb; parentPosInorder++) {
            if (inorder[parentPosInorder] == parent) {
                break;
            }
        }

        if (parentPosInorder > hb) {
            throw new IllegalArgumentException("Your tree is not accurate");
        }

        // proof in diagram : https://bitbucket.org/ameyapatil/pointstonote/commits/a3137e1e5c9f40f28c53b9c62e27f0e8bf81a000
        int numElemsInLeftSubTree = parentPosInorder - lb;

        /**
         * Basically absolutely same as construct Balanced BST from sorted array
         * with this extra junk to be added.
         */
        int leftParentPosPre = pos + 1;
        // proof in diagram : https://bitbucket.org/ameyapatil/pointstonote/commits/458d044f96226e8df1c47775dbe3c8c5ad9ecce4
        int rightParentPosPre = pos + numElemsInLeftSubTree + 1;

        // step 3: recurse
        TreeNode node = new TreeNode(null, null, parent);
        node.left = treeFromPreOrderAndInorder(pre, leftParentPosPre, inorder, lb, parentPosInorder - 1);
        node.right = treeFromPreOrderAndInorder(pre, rightParentPosPre, inorder, parentPosInorder + 1,  hb);

        return node;
    }
\$\endgroup\$
  • \$\begingroup\$ Is the tree reconstruction necessarily deterministic? If the inorder array is [8, 8, 8, 8] and the preorder array is also [8, 8, 8, 8], then what should the result look like? \$\endgroup\$ – 200_success Sep 23 '13 at 18:36
3
\$\begingroup\$

The algorithm looks good to me. Regarding the code, here are a few points:

  1. You don't need to overload the function. Semantically it's a tree builder, and probably the private function can be termed as buildTree.
  2. The following condition should throw the IllegalStateException instead of IllegalArgumentException:

    if (parentPosInorder > hb) {
        throw new IllegalArgumentException("Your tree is not accurate");
    }
    
  3. You can make the code generic by using a generic data type for the node value. Accordingly, the API will be extensible enough.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.