[Math] need help with how to Construct Binary Tree from Inorder traversal

algorithmscomputer sciencedata structuregraph theory

Question : we have the following list J, R, D, G, T, E, M, H, P, A, F, Q
which is inserted in order in an empty binary tree.

This is the inorder traversal :

A, D, E, F, G, H, J, M, P, Q, R, T

construct the binary tree.

The answer is :

I understand that inorder is : You visit the node after you visited his left sub-tree and then you visit the right sub-tree.

I understand how to do it also when u have the given sequence for pre-order and in-order at the same time but i need help understanding what to do when u only have the in-order sequence.

I have no clue why we say that J is the root, i have no clue why F is in the right branch of E and the list goes on…

It seems to me that i am missing out some basic concept to help me understand this, if anyone could explain step by step the process i would greatly appreciate it.

Thanks a lot.

Best Answer

Solution

You are given two clues for how to solve this problem: The result of the Inorder-Tree-Walk, and the order the values are inserted. As another clue, you may use that if a node is inserted into a binary tree, it will always become the root and remain so until it is removed. If a node $x$ is inserted into a tree containing just a single root $y$, then $y$ will become the parent of $x$ and stay so.

Given what you already know from the inorder walk, you should now be able to reconstruct the tree. Since J is inserted first, you know it must be the root. Next, you know that R will be a child of J. To see if it is the left or the right child, you can simply examine the order in the inorder walk.

More information

This sort of tree is called a binary search tree. Let $u$ be a node in the tree, and define $u.\mathit{key}$ to be the value stored in the node (e.g. J or D). A binary search tree has the property that for any given node $u$, then if $x$ is a node in the left subtree of $u$, $x.\mathit{key} \leq u.\mathit{key}$. If $x$ is a node in the right subtree of u, $x.\mathit{key} \geq u.\mathit{key}$.

There is an algorithm for inserting nodes into a binary search tree which makes sure this property is maintained, but you actually don't need it to solve your problem. If, however, you are interested, you can find more information in the excellent book Introduction to Algorithms by Cormen et. al.

Related Solutions

[Math] Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8

So would it be correct for me to go to the lowest node in the lowest level subtree to the left (i.e. 5) and then use that node to overwrite the node I'm trying to delete? So essentially I overwrote the node I wanted to delete 4 with 5 then deleted node 5 and thus: $c_1 =$ B.S.T. after deleting 4 and $c_2 = $ B.S.T. after deleting 10

so:

$c_1$:

and then for deleting 10 I find the smallest node in the right tree which is 11 and I overwrite 10 with that and then delete 11 so:

$c_2:$

[Math] Why is tree not uniquely possible with given preorder and postorder traversal

Consider the trees shown below:

                    1                      1  
                   /                      /  
                  2                      2  
                 /                        \  
                3                          3

Both have preorder $123$, and both have postorder $321$, but they’re not the same binary tree. More generally, if a node has only one child, preorder and postorder do not contain enough information to determine whether that child is a left child or a right child.