Building A Binary Tree (From Post/Pre-Order & In-Order Traversal)

As most of you know, it is possible to build a Binary Tree from either its post-order/pre-order traversal and its in-order traversal. For example, given the following:

Pre-Order: 1 2 4 5 8 9 3 6 0 7
In-Order: 4 2 8 5 9 1 6 0 3 7

You can re-construct the Binary Tree and get the following:

       1
   /       \
  2         3
 / \       / \
4   5     6   7
   / \     \
  8   9     0

Basically, the pre-order traversal will give you the order in which the nodes should be added, and the in-order traversal will give you the position. For example, using the pre-order example, we have "1". Since it's pre-order, which means that it's traversed in the order Root-Left-Right, "1" would be the root node since it appears first. Thus, we create "1" accordingly. Take note of the position of "1" in the in-order traversal. Next, we have "2" (pre-order), which means it's the next node to be created/inserted. Looking at the in-order traversal, we see that "2" is to the left of "1", and thus, "2" would be the left node of "1". We now look at "3" (pre-order), and see that it is to the right of "1" in in-order, and thus add "3" to the left of "1" accordingly.

We now look at "4" (pre-order), and see that it is to the left of "2" (in-order). Next up, is "5", which is to the right of "2". This goes on until the whole tree is created. I figured that since it is quite easy to figure out once you get the concept, why not put it into code? It can be seen that this can be coded recursively, and so I went ahead and implemented it in Java. However, I ran into some problems with the base case, and after doing some search online, I found http://www.dotnetjunkies.com/WebLog/debasish/archive/2006/05/31/139364.aspx, which gave me the solution to the base case I want. Ok, enough talking, and here's the code:

/*
 * Author: Soh Yuan Chin
 * Explanation:
 * Create a tree from its preorder/postorder and inorder
 * The first line of input will have 0 or 1. 0 = preorder. 1 = postorder.
 * Second line of input determines number of nodes.
 * Third line of input contains the pre/post order.
 * Fourth line of input contains the in order.
 *
 * Example Input:
 * 0
 * 10
 * 1 2 4 5 8 9 3 6 0 7
 * 4 2 8 5 9 1 6 0 3 7
 *
 */

import java.util.*;

public class BuildBinaryTree {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BinaryTree bt = new BinaryTree();

        int type = sc.nextInt();
        int numOfNodes = sc.nextInt();
        int[] preOrPost = new int[numOfNodes];
        int[] inOrder = new int[numOfNodes];

        for (int i = 0; i < numOfNodes; i++) {
            preOrPost[i] = sc.nextInt();
        }

        for (int i = 0; i < numOfNodes; i++) {
            inOrder[i] = sc.nextInt();
        }

        bt.buildTree(preOrPost, inOrder, type);
        bt.preOrder();
        bt.inOrder();
        bt.postOrder();
    }

}

class TreeNode {
    protected int number;
    protected TreeNode left;
    protected TreeNode right;

    TreeNode(int number) {
        this.number = number;
    }
}

class BinaryTree {

    private TreeNode root;
    private int size;

    BinaryTree() {
        root = null;
        size = 0;
    }

    // Building Tree    
    public void buildTree(int[] preOrPost, int[] inOrder, int type) {
        if (type == 0)
            root = buildPreOrderTree(preOrPost, inOrder, 0, 0, preOrPost.length);
        else if (type == 1) {
            // reverse the array. exchange the first and last.
            for (int left=0, right=preOrPost.length-1; left < right; left++, right--) {
                int temp = preOrPost[left];
                preOrPost[left] = preOrPost[right];
                preOrPost[right] = temp;
            }

            root = buildPostOrderTree(preOrPost, inOrder, 0, 0, preOrPost.length);
        }

    }

    private TreeNode buildPostOrderTree(int[] preOrPost, int[] inOrder, int curr, int start, int end) {
        TreeNode currNode = null;

        if (end-start == 1) {
            currNode = new TreeNode(inOrder[start]);
        }
        else {
            int k = 0;
            for (int i = start; i < end; i++) {
                if (preOrPost[curr] == inOrder[i]) {
                    k = i;
                    break;
                }
            }

            if (k > 0) {
                currNode = new TreeNode(inOrder[k]);
                currNode.right = buildPostOrderTree(preOrPost, inOrder, curr+1, k+1, end);
                currNode.left = buildPostOrderTree(preOrPost, inOrder, curr+(k-start), start, k);
            }
        }

        return currNode;
    }


    private TreeNode buildPreOrderTree(int[] preOrPost, int[] inOrder, int curr, int start, int end) {
        TreeNode currNode = null;

        if (end-start == 1) {
            currNode = new TreeNode(inOrder[start]);
        }
        else {
            int k = 0;
            for (int i = start; i < end; i++) {
                if (preOrPost[curr] == inOrder[i]) {
                    k = i;
                    break;
                }
            }

            if (k > 0) {
                currNode = new TreeNode(inOrder[k]);
                currNode.left = buildPreOrderTree(preOrPost, inOrder, curr+1, start, k);
                currNode.right = buildPreOrderTree(preOrPost, inOrder, curr+1+(k-start), k+1, end);
            }
        }

        return currNode;
    }

    // Traverse
    public void preOrder() {
        System.out.print("Pre-Order: ");
        preOrder(root);
        System.out.println();
    }

    private void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.number + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    public void postOrder() {
        System.out.print("Post-Order: ");
        postOrder(root);
        System.out.println();
    }

    private void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.number + " ");
        }
    }

    public void inOrder() {
        System.out.print("In-Order: ");
        inOrder(root);
        System.out.println();
    }

    private void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.number + " ");
            inOrder(node.right);
        }
    }

    public void levelOrder() {
        System.out.print("Level-Order: ");
        levelOrder(root);
        System.out.println();
    }

    private void levelOrder(TreeNode node) {
        if (node != null) {
            Queue<TreeNode> tempQ = new LinkedList<TreeNode>();
            tempQ.offer(node);        
            TreeNode temp = null;

            while (!tempQ.isEmpty()) {
                temp = tempQ.poll();
                System.out.print(temp.number + " ");

                if (temp.left != null)
                    tempQ.offer(temp.left);
                if (temp.right != null)
                    tempQ.offer(temp.right);
            }
        }
    }
}

Take note that the above code is able to do both pre-order/post-order and in-order building of tree. Also, you should get an output of printing out the different traversals of the newly-built tree. You can enable level-order traversal by adding the method call to main(), the levelOrder() method has already been implemented. Lastly, I implemented post-order building of tree by reversing the array of elements first. If you do not want to do that, simply modify the values of curr, start, and end accordingly.

Below are 2 test cases you can try using. Simply save them as a text file, example "test.txt", and use input redirection "java BuildBinaryTree < test.txt".

Post-Order Test Case:

1
10
4 8 9 5 2 0 6 7 3 1
4 2 8 5 9 1 6 0 3 7

Pre-Order Test Case:

0
10
1 2 4 5 8 9 3 6 0 7
4 2 8 5 9 1 6 0 3 7

I hope this has been useful for some of you =)!