Construct Full Binary Tree from given preorder and postorder traversals

Reference
http://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/

Problem statement :-
A Full Binary Tree is a binary tree where every node has either 0 or 2 children

It is not possible to construct a general Binary Tree from preorder and postorder traversals (See this). But if know that the Binary Tree is Full, we can construct the tree without ambiguity. Let us understand this with the help of following example.

Let us consider the two given arrays as pre[] = {1, 2, 4, 8, 9, 5, 3, 6, 7} and post[] = {8, 9, 4, 5, 2, 6, 7, 3, 1};
In pre[], the leftmost element is root of tree. Since the tree is full and array size is more than 1. The value next to 1 in pre[], must be left child of root. So we know 1 is root and 2 is left child. How to find the all nodes in left subtree? We know 2 is root of all nodes in left subtree. All nodes before 2 in post[] must be in left subtree. Now we know 1 is root, elements {8, 9, 4, 5, 2} are in left subtree, and the elements {6, 7, 3} are in right subtree.


                  1
                /   \
               /      \
     {8, 9, 4, 5, 2}     {6, 7, 3}
We recursively follow the above approach and get the following tree.

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

My Java implementation

import java.util.Queue;

import java.util.concurrent.LinkedBlockingQueue;

class TreeNode {

  

    // data members

 public int key;

 public char charkey;

    public TreeNode left;

    public TreeNode right;

  

    // Constructor

    public TreeNode(int key) { this.key = key; left = null; right = null; }

    public TreeNode(char charkey) { this.charkey = charkey; left = null; right = null; }

  

    // Methods to set left and right subtrees

    public void setLeft(TreeNode left)   { this.left = left; }

    public void setRight(TreeNode right) { this.right = right; }

    

    public static void printLevelOrder(TreeNode root)

    {

      Queue<TreeNode> queue = new LinkedBlockingQueue<TreeNode>(); 

      

      while(root != null){

       System.out.println(root.charkey);

       if(root.left!=null){

        queue.add(root.left);

       }

       if(root.right!=null){

        queue.add(root.right);

       }

       root = queue.poll();

      }

    }

}

 public class ConstructTreeFromTraversal {

  

   int preOrderIndex=0;

   String inorder, preorder ,postorder;

  

 

 public static void main(String[] args) {

/* postorder preorder  test */

ConstructTreeFromTraversal obj = new ConstructTreeFromTraversal();

obj.postorder="894526731";

obj.preorder="124895367";

TreeNode root = obj.constructTree_Preorder_Postorder();

TreeNode.printLevelOrder(root);

System.out.println("Done");

}

 public TreeNode constructTree_Preorder_Postorder(){

return constructTree_Preorder_Postorder_inernal(postorder);

}

public TreeNode constructTree_Preorder_Postorder_inernal(String postorder){

if(postorder.equals("")){

return null;

}

// preOrderIndex which is initialized as zero indicates current position in preorder

// that is to be considered as root

char rootKey = preorder.charAt(preOrderIndex);

preOrderIndex++;

TreeNode root = new TreeNode(rootKey);

if(postorder.length()>1){

// In post-order last element will be root. So we will omit it for further process

// And split the string into two parts based on left child

String tempStringWithoutRoot = postorder.substring(0,postorder.length()-1);

char leftChildKEy = preorder.charAt(preOrderIndex);

if(tempStringWithoutRoot.length()>1){

String [] child = tempStringWithoutRoot.split(leftChildKEy+"");

TreeNode leftChild = constructTree_Preorder_Postorder_inernal(child[0]+leftChildKEy);

root.setLeft(leftChild);

if(child.length>1){

TreeNode rightChild = constructTree_Preorder_Postorder_inernal(child[1]);

root.setRight(rightChild);

}

}else{

TreeNode leftChild = constructTree_Preorder_Postorder_inernal(tempStringWithoutRoot);

}

}

return root;

}

}

Output

1

2

3

4

5

6

7

8

9

Done