Binary tree reconstruction from IN and PRE or POST order traversals

Reconstructing binary tree from Inorder and Preorder traversal is pretty straighforward. The idea is to number the Inorder sequence in increasing order and use that number as a key to insert into Binary Search Tree. The insertion into BST is carried out in the order given in Preorder traversal.

Example:
Inorder: DBEAFCG
Preorder: ABDECFG

Now number the inorder traversal:DBEAFCG (1234567). Thus the preorder traversal will be ABDECFG (4213657)

Insert the items picking them in preorder into BST. So first you will insert 4(A), then 2(B), 1(D) and so on. This will give you the original tree from which traversals are generated.

Code for it is given below

//Tree node
class Node {

public Node left;
public Node right;

//key
public int key;

//label of the node
public char label;

public Node(Node left, Node right, int key, char label){
this.left = left;
this.right = right;
this.value = val;
this.key= key;
}


public Node(int key, char label) {
this(null, null, key,label);
}


}

//Binary Search Tree
class Tree {
public Node root;

public Tree() {
this(null);
}
public Tree(Node root) {
this.root = root;
}


public void insert(int key, char label) {

Node node = new Node(key, label);
if(root == null) {
root = node;
return;
}

Node temp = root;
Node parent = root;

while(temp != null) {
parent = temp;
if ( key < temp =" temp.left;" temp ="=" left =" node;" temp =" temp.right;" temp ="=" right =" node;" table =" new" count =" 0;" bst =" new">

Reconstruction from Inorder and Postorder

Steps are pretty much the same for Postorder too. But while inserting into BST we start from last element of the traversal and continue on to first.