Im doing an assignment on building a binary tree from the preorder and inorder traversals (a char in each Node) and im trying to wrap my brain around how to build the actual tree.
Here is my thought process on how to accomplish this:
- store the first entry in the preorder as the root node
- search the inorder for that entry.
- take the chars to the left of the root node and save them as a char array.
- take the chars to the right of the root node and save them as a char array.
- make a new tree, with the root as the parent and its 2 children being the left and right char arrays.
- keep going recursively until the preorder length is 0.
I have steps 1-4 taken care of, but im not too sure how to properly build my tree, and was wondering if anyone had any pointers. Thank you.
6 Answers 6
Do the recursion before building the new tree. So, your list would look like this:
- If the arrays have length 1, just return a leaf node with this single item in it. (This is the recursion foundation.) (O(1))
- Store the first entry in the preorder array as the root node. (O(1))
- Search the inorder array for that entry. (O(n))
- Take the chars to the left of the root node in the inorder array and save them as a char array. Take the same amount of characters from the preorder array (after the root). (O(n), or O(1) when just throwing pointers/indexes around.)
- Take the chars to the right of the root node and save them as a char array. Take the same amount of characters from the preorder array (after the first part – that should be just the remainding part). (O(n), or O(1) when just throwing pointers/indexes around.)
- Recursively make a tree from both left char arrays.
- Recursively make a tree from both right char arrays.
- Combine both trees with your root node. (O(1).)
The non-recursive parts can be done in O(n) overall, and summing them up for each recursion level is also O(n) each. The total runtime thus depends on the number of recursion levels. If you have a approximately balanced tree, the depth is O(log n), thus we get to O(n · log n) at all. As the only necessarily slow part is the search of the root node in the inorder array, I guess we could optimize that even a bit more if we know more about the tree.
In the worst case we have one recursion level for each node in the tree, coming to complexity O(n·n).
Example: Preorder ABCDEF, Inorder FEDCBA, Tree:
+---+
| A |
++--+
|
+---+ |
| B +<--+
++--+
|
+---+ |
| C +<--+
++--+
|
+---+ |
| D +<--+
++--+
|
+---+ |
| E +<--+
++--+
|
+---+ |
| F +<--+
+---+
5 Comments
O(n· log n). Worst case will likely be O(n²) (something like just a linked list, i.e. where the root node is always last in the search).See my answer to this question. You build the tree by adding nodes in pre-order sequence, but by using the inorder position as comparator.
3 Comments
You can use the below code, I just wrote for the same problem. It works for me.
public class TreeFromInorderAndPreOrder {
public static List<Integer> inOrder = new ArrayList<Integer>();
public static List<Integer> preOrder = new ArrayList<Integer>();
public static void main(String[] args) {
Node root = new Node();
root.createRoot(5);
for(int i = 0 ; i < 9 ; i++){
if(i != 5){
root.insert(i);
}
}
inOrder(root);
preOrder(root);
for(Integer temp : inOrder){
System.out.print(temp + " ");
}
System.out.println();
for(Integer temp : preOrder){
System.out.print(temp + " ");
}
Node node1 = null;
node1 = reConstructTree(root, (ArrayList<Integer>) inOrder, true);
System.out.println();
inOrder(node1);
for(Integer temp : inOrder){
System.out.print(temp + " ");
}
System.out.println();
for(Integer temp : preOrder){
System.out.print(temp + " ");
}
}
public static void inOrder(Node node){
if(node!= null){
inOrder(node.leftchild);
inOrder.add(node.key);
inOrder(node.rightChild);
}
}
public static void preOrder(Node node){
if(node != null){
preOrder.add(node.key);
preOrder(node.leftchild);
preOrder(node.rightChild);
}
}
public static Node reConstructTree(Node root, ArrayList<Integer> inOrder,
boolean isLeft){
if(preOrder.size() != 0 && inOrder.size() != 0){
return null;
}
Node node = new Node();
node.createRoot(preOrder.get(0));
if(root != null && isLeft){
root.leftchild = node;
}else if(root != null && !isLeft){
root.rightChild = node;
}
int indx = inOrder.get(preOrder.get(0));
preOrder.remove(0);
List<Integer> leftInorder = getSublist(0, indx);
reConstructTree(node, (ArrayList<Integer>) leftInorder, true);
List<Integer> rightInorder = getSublist(indx+1, inOrder.size());
reConstructTree(node, (ArrayList<Integer>)rightInorder, false);
return node;
}
public static ArrayList<Integer> getSublist(int start, int end){
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = start ; i < end ; i++){
list.add(inOrder.get(i));
}
return list;
}
}
Comments
I have written a sample program using divide and conquer approach using recursion in java
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeNode {
private char data;
public char getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
public BinaryTreeNode getLeft() {
return left;
}
public void setLeft(BinaryTreeNode left) {
this.left = left;
}
public BinaryTreeNode getRight() {
return right;
}
public void setRight(BinaryTreeNode right) {
this.right = right;
}
private BinaryTreeNode left;
private BinaryTreeNode right;
public static void levelTravesal(BinaryTreeNode node)
{
Queue queue = new LinkedList();
if(node == null)
return;
queue.offer(node);
queue.offer(null);
int level =0;
while(!queue.isEmpty())
{
BinaryTreeNode temp = (BinaryTreeNode) queue.poll();
if(temp == null)
{
System.out.println("Level: "+level);
if(!queue.isEmpty())
queue.offer(null);
level++;
}else {
System.out.println(temp.data);
if(temp.getLeft()!=null)
queue.offer(temp.getLeft());
if(temp.getRight()!=null)
queue.offer(temp.getRight());
}
}
}
static int preIndex = 0;
public static void main(String[] args) {
if(args.length < 2)
{
System.out.println("Usage: preorder inorder");
return;
}
char[] preOrderSequence = args[0].toCharArray();
char[] inOrderSequence = args[1].toCharArray();
//char[] preOrderSequence = {'A','B','D','E','C','F'};
//char[] inOrderSequence = "DBEAFC".toCharArray();
if(preOrderSequence.length != inOrderSequence.length)
{
System.out.println("Pre-order and in-order sequences must be of same length");
return;
}
BinaryTreeNode root = buildBinaryTree(preOrderSequence, inOrderSequence, 0, preOrderSequence.length-1);
System.out.println();
levelTravesal(root);
}
static BinaryTreeNode buildBinaryTree(char[] preOrder, char[] inOrder, int start, int end)
{
if(start > end)
return null;
BinaryTreeNode rootNode = new BinaryTreeNode();
rootNode.setData(preOrder[preIndex]);
preIndex++;
//System.out.println(rootNode.getData());
if(start == end)
return rootNode;
int dataIndex = search(inOrder, start, end, rootNode.getData());
if(dataIndex == -1)
return null;
//System.out.println("Left Bounds: "+start+" "+(dataIndex-1));
rootNode.setLeft(buildBinaryTree(preOrder, inOrder, start, dataIndex - 1));
//System.out.println("Right Bounds: "+(dataIndex+1)+" "+end);
rootNode.setRight(buildBinaryTree(preOrder, inOrder, dataIndex+1, end));
return rootNode;
}
static int search(char[] inOrder,int start,int end,char data)
{
for(int i=start;i<=end;i++)
{
if(inOrder[i] == data)
return i;
}
return -1;
}
}
Comments
Here is a mathematical approach to achieve the thing in a very simplistic way :
Language used : Java
`
/*
Algorithm for constructing binary tree from given Inorder and Preorder traversals.
Following is the terminology used :
i : represents the inorder array supplied
p : represents the preorder array supplied
beg1 : starting index of inorder array
beg2 : starting index of preorder array
end1 : ending index of inorder array
end2 : ending index of preorder array
*/
public static void constructTree(Node root, int[] i, int[] p, int beg1, int end1, int beg2, int end2)
{
if(beg1==end1 && beg2 == end2)
{
root.data = i[beg1];
}
else if(beg1<=end1 && beg2<=end2)
{
root.data = p[beg2];
int mid = search(i, (int) root.data);
root.left=new Node();
root.right=new Node();
constructTree(root.left, i, p, beg1, mid-1, beg2+1, beg2+mid-beg1);
System.out.println("Printing root left : " + root.left.data);
constructTree(root.right, i, p, mid+1, end1, beg2+1+mid-beg1, end2);
System.out.println("Printing root left : " + root.right.data);
}
}
`
You need invoke the function by following code :
int[] i ={4,8,7,9,2,5,1,6,19,3,18,10}; //Inorder
int[] p ={1,2,4,7,8,9,5,3,6,19,10,18}; //Preorder
Node root1=new Node();
constructTree(root1, i, p, 0, i.length-1, 0, p.length-1);
In case you need a more elaborate explanation of code please mention it in the comments. I would be happy to help :).
Comments
The accepted answer can be further optimized regarding step #3: Search the inorder array for that entry. (O(n))
If we preprocess the inorder array, we pay the Θ(n) cost once for all instead of paying O(n) for each recursion, hence get a boost on hidden constants despite the Big-O-notation being still O(n).
See Python implementation below:
def buildTree(self, inorder, postorder):
memoi = {}
for i, val in enumerate( inorder ):
memoi[val] = i
def myFunc( start1, end1, start2, end2 ):
if start1 == end1:
return None
root = TreeNode( postorder[end2 - 1] )
i = memoi[root.val]
root.left = myFunc( start1, i, start2, start2 + i - start1 )
l = end1 - ( i + 1 )
root.right = myFunc( i + 1, end1, end2 - 1 - l, end2 - 1 )
return root
return myFunc( 0, len( inorder ), 0, len( postorder ) )