constructing a binary tree from its inorder and preorder traversals - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# constructing a binary tree from its inorder and preorder traversals

Posts: 14Member
Given: Two arrays representing the inorder and preorder traversals of a binary tree.....

ex: Inorder: 2 9 3 5 4 1 7 6 8
Preorder:1 2 3 9 4 5 6 7 8

I want to construct the binary tree from this two arrays.....

Any suggestions would be welcome.....

thanks,
prakash.

• Posts: 770Member ✭✭✭
: Given: Two arrays representing the inorder and preorder traversals of a binary tree.....
:
: ex: Inorder: 2 9 3 5 4 1 7 6 8
: Preorder:1 2 3 9 4 5 6 7 8
:
:
: I want to construct the binary tree from this two arrays.....
:
: Any suggestions would be welcome.....
:
: thanks,
: prakash.
:
[blue]As I understand it, an inorder traversal would only give you the elements in their sorted order regardless of the order they were initially stored in. Therefore it is impossible to determine the original shape of the tree given an inorder sequence of values.

As I have found in the past, looking at the preorder output of the contents of a binary tree is an easy way to figure out the original shape. Given your values, the tree must look like this:
[code]
1

2

3

9
/
4

5

6

7

8
[/code]This isn't much of a binary tree is it? Looks just like a sequential linked list at this point. This is in serious need of balancing.[/blue]
• Posts: 14Member
: : Given: Two arrays representing the inorder and preorder traversals of a binary tree.....
: :
: : ex: Inorder: 2 9 3 5 4 1 7 6 8
: : Preorder:1 2 3 9 4 5 6 7 8
: :
: :
: : I want to construct the binary tree from this two arrays.....
: :
: : Any suggestions would be welcome.....
: :
: : thanks,
: : prakash.
: :
: [blue]As I understand it, an inorder traversal would only give you the elements in their sorted order regardless of the order they were initially stored in. Therefore it is impossible to determine the original shape of the tree given an inorder sequence of values.
:
: As I have found in the past, looking at the preorder output of the contents of a binary tree is an easy way to figure out the original shape. Given your values, the tree must look like this:
: [code]
: 1
:
: 2
:
: 3
:
: 9
: /
: 4
:
: 5
:
: 6
:
: 7
:
: 8
: [/code]This isn't much of a binary tree is it? Looks just like a sequential linked list at this point. This is in serious need of balancing.[/blue]
:

hi, the thing is u have to use the information in both the arrays to determine the tree.... i've come up with a solution.....
The first element in the preorder array will be the root. Now traverse the inorder array till u find that inorder array element. Now all those elements in the preorder array which are to the left of the element found will come in the left subtree and all those elements to the right will come in the right subtree....

Recursively do the same till u exhaust all the elements in the array.
Thanks for ur suggestion.bye.

prakash.
• Posts: 4Member
: Given: Two arrays representing the inorder and preorder traversals of a binary tree.....
:
: ex: Inorder: 2 9 3 5 4 1 7 6 8
: Preorder:1 2 3 9 4 5 6 7 8
:
:
: I want to construct the binary tree from this two arrays.....
:
: Any suggestions would be welcome.....
:
: thanks,
: prakash.
:

Hi,

Can you share the C++ code, if you have? I need this for my assignment.
• Posts: 1Member
please if you find pesude code of this problem set in the messageboar

• Posts: 770Member ✭✭✭
: please if you find pesude code of this problem set in the messageboar
:

You mean pseudocode? Generally you should not bump threads that are more than perhaps a week or so old. What you should do is make a new post explaining your problem and perhaps with a link to this old post as a reference. That said, a C++ version with the important bit in pseudocode is as follows:

[code]
struct node
{
int data;
node* lptr;
node* rptr;
node(int val) : lptr(0), rptr(0), data(val)
{
}
};

node* buildtree(int* inorder,int* preorder,int left,int right,int& current)
{
1. Test if left is equal to right and return NULL if it is.
2. Create a new temporary node with value of preorder[current].
3. Return this new temporary node if left+1 is equal to right.
4. Search starting from inorder+left up to inorder+right and get
an int pointer to the element that has the same value as
preorder[current].
5. Find the distance from the start of the inorder array to this
pointer, call it position.
6. If position is greater than left then...
6a. Increment current
6b. Set the lptr of the temporary node equal to the return
value of buildtree(inorder,preorder,left,position,current)
7. If position+1 is less than right then...
7a. Increment current
7b. Set the rptr of the temporary node equal to the return
value of buildtree(inorder,preorder,position+1,right,current)
8. Return the temporary node
}

int main()
{
int preorder[] = { 6, 15, 1, 23, 9, -9, 22 };
int inorder[] = { 23, 1, 15, 9, 6, 22, -19 };
int count = 0;
node* root = buildtree(inorder,preorder,0,7,count);
// root now points to the root of the binary-search tree
// built from the two arrays.
}
[/code]