105 Construct Binary Tree from Preorder and Inorder Traversal

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

Related Data Structure knowledge:

DFS:

To start this problem, we need to really understand the Depth-First Search by hear. So here I will sort out some related points about it before solve the problem

The general recursive pattern for traversing a (non-empty) binary tree is this: At node N you must do these three things: (L) recursively traverse its left sub-tree. When this step is finished you are back at N again. (R) recursively traverse its right sub-tree. When this step is finished you are back at N again. (N) Actually process N itself.

1. Pre-order: F, B, A, D, C, E, G, I, H
   1. Current(Root): Display the data part of the root (or current node).
   2. Left sub-tree: Traverse the left sub-tree by recursively calling the pre-order function.
   3. Right sub-tree: Traverse the right subtree by recursively calling the pre-order function.
2. In-order: A, B, C, D, E, F, G, H, I
   1. Left
   2. Current
   3. Right

In this order, the data is retrieved in a sorted order. if it's number

1. Post-order: A, C, E, D, B, H, I, G, F
   1. Left
   2. Right
   3. Current

The logic flow:

1. For pre-order, the first element also always the root of binary tree;
2. For in-order, the order is always sorted;
3. What's the connection between pre-order and in-order in terms of the root element? -> mark the root element in in-order result -> Root element will divide the in-order into left sub-tree and right sub-tree; -> The two sub-trees are also shown in the pre-order;
4. After we got the first left/right sub-tree, keep dividing it until it only has single note of each sub-tree.

Steps:

1. Get the first element of pre-order and then search the root in in-order result
2. Find range for left sub-tree and right sub-tree
3. Recursively divide down to construct sub-trees and finally connect it to the root

The obstacle I encountered:

1. At the beginning, I misinterpreted the problem. I didn't realize we will be given both pre-order and in-order of the binary tree. I assumed we are only given one order each time. But yeah, it might be just ME ><
2. The root value will always come from preorder, and index of that node we will find from inorder result
3. three parameters need to be taken care of:
   1. The updated start index in pre-order result;
   2. Two boundary of in-order substree

Way to imporve the efficiency:

1. Using hashtable to store the index of inorder

code:

    Hashtable<Integer,Integer> inorderIndex = new Hashtable<Integer, Integer>();

    public TreeNode buildSubTree(int[] preorder, int pIndex, int[] inorder, int iStart, int iEnd){
        if(preorder == null || inorder == null || iEnd <= 0){
            return null;
        }
        int rootValue = preorder[pIndex];
        TreeNode root = new TreeNode(rootValue);
        int inorderPos = inorderIndex.get(rootValue);

        int leftLength = inorderPos -iStart;
        int rightLength = iEnd - leftLength -1;

        root.left = buildSubTree(preorder, pIndex+1, inorder, iStart, leftLength);
        root.right = buildSubTree(preorder, pIndex+leftLength+1, inorder, inorderPos+1, rightLength);
        return root;
            }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null){
            return null;
        }
        int n = preorder.length;
        inorderIndex.clear();

        for(int i=0; i<preorder.length; i++)
        {
            inorderIndex.put(inorder[i], i);
        }
        return buildSubTree(preorder, 0, inorder, 0, n);

    }