Construct Binary Tree from Preorder and Inorder traversal | Construct Binary Search Tree
firstly we will understand the basics of Inorder, Preorder and Postorder, here i given a example
- A+B (Inorder)
- AB+ (Post order)
- +AB (Preorder)
Golden Rule:-
- Preorder---- Root left Right
- Inorder ---- left Root Right
- Postorder--- left right Root
Let's take an example to create Binary search tree using given Inorder and Preorder values
Inorder 2-3-4-5-6-8-10
Preorder 5-3-2-4-8-6-10
Step-1:- as we know preorder visits the root node first then the first value always represent the root node of the binary search tree.
therefore 5 is root node, and From above Inorder traversal, we know that a node’s left subtree is traversed before it followed by right subtree. Therefore all the values to the left of 5 in inorder belong to its left subtree and all values to the right belong to its right subtree.
Step-2:- now we follow the same rules, as second element in preorder is 3. So our parent node of left subtree will be 3, and using inorder traversal we find the left and right child of parent node 3.
Step-3:- Now for right subtree do the same as above. 8 becomes the root. And 6 will be left child and 10 will be right child.
so above is resultant Binary search tree for given inorder and preorder values
0 Comments
if u have any doubts please let me know,