Objective: – Given a inorder and preorder traversal, construct a binary tree from that.
Input: Inorder and preorder traversals
Similar Problem: Construct a binary tree from given Inorder and Postorder Traversal
Approach:
int [] inOrder = {2,5,6,10,12,14,15};
int [] preOrder = {10,5,2,6,14,12,15};
- First element in preorder[] will be the root of the tree, here its 10.
- Now the search element 10 in inorder[], say you find it at position i, once you find it, make note of elements which are left to i (this will construct the leftsubtree) and elements which are right to i ( this will construct the rightSubtree).
- See this step above and recursively construct left subtree and link it root.left and recursively construct right subtree and link it root.right.
- See the picture and code.
Complete Code:
| public class MakeTreefromInorderAndPreorder { | |
| public static int pIndex=0; | |
| public Node makeBTree(int [] inOrder, int [] preOrder, int iStart, int iEnd ){ | |
| if(iStart>iEnd){ | |
| return null; | |
| } | |
| Node root = new Node(preOrder[pIndex]);pIndex++; | |
| if(iStart==iEnd){ | |
| return root; | |
| } | |
| int index = getInorderIndex(inOrder, iStart, iEnd, root.data); | |
| root.left = makeBTree(inOrder,preOrder,iStart, index–1); | |
| root.right = makeBTree(inOrder,preOrder,index+1, iEnd); | |
| //} | |
| return root; | |
| } | |
| public int getInorderIndex(int [] inOrder, int start, int end, int data){ | |
| for(int i=start;i<=end;i++){ | |
| if(inOrder[i]==data){ | |
| return i; | |
| } | |
| } | |
| return –1; | |
| } | |
| public void printINORDER(Node root){ | |
| if(root!=null){ | |
| printINORDER(root.left); | |
| System.out.print(" " + root.data); | |
| printINORDER(root.right); | |
| } | |
| } | |
| public static void main (String[] args) throws java.lang.Exception | |
| { | |
| int [] inOrder = {2,5,6,10,12,14,15}; | |
| int [] preOrder = {10,5,2,6,14,12,15}; | |
| MakeTreefromInorderAndPreorder i = new MakeTreefromInorderAndPreorder(); | |
| Node x = i.makeBTree(inOrder, preOrder, 0, inOrder.length–1); | |
| System.out.println("Constructed Tree : "); | |
| i.printINORDER(x); | |
| } | |
| } | |
| class Node{ | |
| int data; | |
| Node left; | |
| Node right; | |
| public Node (int data){ | |
| this.data = data; | |
| left = null; | |
| right = null; | |
| } | |
| } |
Output:
Constructed Tree : 2 5 6 10 12 14 15
Broken method.
No solution for —
ADFGHKLPQRWZ(preorder)
GFHKDLAWRQPZ(inorder)
GKHFLDWRQZPA (Postorder)