A binary tree generates the sequence of abcdefg for an in order traversal and the sequence acbgfed for post order traversal what are the total of nodes in the left sub tree of these binary tree
Answers
The total nodes in the left subtree will be 3.
1. It is given:
In[ ] = {a, b, c, d, e, f, g}
Post[ ] = {a, c, b, g, f, e, d}
2. The first node will be the last node in Post[ ]. Therefore, the first node of the binary tree will be d.
3. Everything to the left of 'd' in In[ ] will be in the left subtree and everything to the right of 'd' will be in the right subtree.
Left subtree = {a, b, c}, Right subtree = {e, f, g}
4. Now, we will follow the above process for {a, b, c} and {e, f ,g}.
5. (a) For the left child of root, Post[ ] = {a, c, b} and In[ ] = {a, b, c}
(b) For the right child of root, Post[ ] = {g, f, e} and In[ ] = {e, f, g}
6. The tree will be:
d
/ \
b e
/ \ \
a c f
\
g
#SPJ3
According to the question;
a, b, c, d, e, f, g = In[ ]
a, c, b, g, f, e, d =Post [ ]
- In Post[], the first node will be the last node. As a result, the binary tree's first node will be d.
- Everything in In[] to the left of 'd' is in the left subtree, and everything to the right of 'd' is in the right subtree.
Right subtree = {e, f, g}
Left subtree = {a, b, c}
- We will now repeat the process for {a, b, c} and {e, f, g}
For the root's left child, Post[] = {a, c, b} and In[] = {a, b, c}
For the root's right child, Post[] = {g, f, e} and In[] = {e, f, g}
The total number of nodes in the left subtree will be 3.
#SPJ2