[alok9shm]

Suppose we have a sequence of nodes of a binary tree in Preorder and Inorder traversal scheme:

[table]
[row]
[cell]PreOrder [/cell]
[cell]G [/cell]
[cell]B [/cell]
[cell]Q [/cell]
[cell]A [/cell]
[cell]C [/cell]
[cell]K [/cell]
[cell]F [/cell]
[cell]P [/cell]
[cell]D [/cell]
[cell]E [/cell]
[cell]R [/cell]
[cell]H [/cell]
[/row]
[row]
[cell]InOrder [/cell]
[cell]Q [/cell]
[cell]B [/cell]
[cell]K [/cell]
[cell]C [/cell]
[cell]F [/cell]
[cell]A [/cell]
[cell]G [/cell]
[cell]P [/cell]
[cell]E [/cell]
[cell]D [/cell]
[cell]H [/cell]
[cell]R [/cell]
[/row]
[/table]

I've got to construct a Binary Tree using the Traversal Data above. I'm sure G is the Root node, as its the first element in Preorder traversal. But I can't figure out how to proceed finding the Left and Right Child. I don't need any code to implement this. All I need is the logic to do this. Thanks

[Souvarine]

My english is too poor, so I can't explain you the logic for finding solution, but binary tree is in the code tag.
I hope it will help you.

Code:

..........G.......... ..........|.......... ......../...\........ ....../.......\...... .....B.........P..... ..../.\......./.\.... ...Q...A.....D...R... .......|.....|...|... .......C.....E...H... ....../.\............ .....K...F...........

[alok9shm]

My english is too poor, so I can't explain you the logic for finding solution, but binary tree is in the code tag.
I hope it will help you.


..........G..........
..........|..........
......../...\........
....../.......\......
.....B.........P.....
..../.\......./.\....
...Q...A.....D...R...
.......|.....|...|...
.......C.....E...H...
....../.\............
.....K...F...........

Thats grateful of you to write down that tree in text. lol. Lets see if I can understand something...Chances are less as I've checked my textbooks and found the constructed trees but couldn't understand how it got created.
Anyways, the green edges/connectors are at 90' angle.
How do I know if they are meant to be / or \.

[Souvarine]

My english is too poor, so I can't explain you the logic for finding solution, but binary tree is in the code tag.
I hope it will help you.


..........G..........
..........|..........
......../...\........
....../.......\......
.....B.........P.....
..../.\......./.\....
...Q...A.....D...R...
.......|.....|...|...
.......C.....E...H...
....../.\............
.....K...F...........

Thats grateful of you to write down that tree in text. lol. Lets see if I can understand something...Chances are less as I've checked my textbooks and found the constructed trees but couldn't understand how it got created.
Anyways, the green edges/connectors are at 90' angle.
How do I know if they are meant to be / or \.

In my original post tree looks fine :p (at least to me?)
Anyway, 'C' is under 'A', 'E' is under 'D' and 'H' is under 'R'.

My advice, just take solved examples and try to solve them by yourself again without that much looking. After few examples you should see some logic between Preorder and Inorder.

[alok9shm]

In my original post tree looks fine :p (at least to me?)
Anyway, 'C' is under 'A', 'E' is under 'D' and 'H' is under 'R'.

My advice, just take solved examples and try to solve them by yourself again without that much looking. After few examples you should see some logic between Preorder and Inorder.

Yes! the tree looks fine and green with fruits and leaves, but I can't understand if C E and H are Left child or right Child of A D and R respectively, as the lines are pointing southwards, instead of going South-East or South-West.

[Souvarine]

In my original post tree looks fine :p (at least to me?)
Anyway, 'C' is under 'A', 'E' is under 'D' and 'H' is under 'R'.

My advice, just take solved examples and try to solve them by yourself again without that much looking. After few examples you should see some logic between Preorder and Inorder.

Yes! the tree looks fine and green with fruits and leaves, but I can't understand if C E and H are Left child or right Child of A D and R respectively, as the lines are pointing southwards, instead of going South-East or South-West.

'A' has only one child, and that is 'C'.
'D' also has only one child, and that is 'E'.
'R' also has only one child, and that is 'H'.

That is the reason why I used lines pointing southwards. I hope it is understandably now :p

Hint: copy-paste tree in plain text editor with monospace font and it will be clear

[Psycho_Coder]

@alok9shm Have you checked the answer from your text book. Does it looks good enough ?

I think there is some problems with his solution. So confirm me whether his answer matches from your textbook else I will post my result

[alok9shm]

@alok9shm Have you checked the answer from your text book. Does it looks good enough ?

I think there is some problems with his solution. So confirm me whether his answer matches from your textbook else I will post my result

This question isn't from any textbook, so I haven't got the answer to it.
Yes, I guess he messed up with the children of D.



This is my try, let me know if its correct. Spent the last night trying to understand other examples of this type in my book.

[Psycho_Coder]

@alok9shm Have you checked the answer from your text book. Does it looks good enough ?

I think there is some problems with his solution. So confirm me whether his answer matches from your textbook else I will post my result

This question isn't from any textbook, so I haven't got the answer to it.
Yes, I guess he messed up with the children of D.



This is my try, let me know if its correct. Spent the last night trying to understand other examples of this type in my book.

Exactly he did mess up with the inorder. I got the same answer as you have shown now.
Okay so have you understood the process.

[alok9shm]

Exactly he did mess up with the inorder. I got the same answer as you have shown now.
Okay so have you understood the process.

Ah!! Finally!! Yes. To conclude:

Step 1: Note the 1st element in the Preorder as the Root node.
Step 2: InCircle the noted node in the Inorder list. Now, the elements to the left of the circled elements form the Left Subtree, and Right one form the Right subtree.
Step 3: Repeat Steps 1 to 3 for the remaining elements.

Thank You.

Closing this thread.