need help with how to Construct Binary Tree from Inorder traversal 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.
 A: 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.
