If the preorder and inorder traversal of the binary tree is ABDEFCGHULK and DBFEAGCLIHK
respectively so what is the postorder traversal.?
Answers
Answer:
Uses of Inorder
In case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal s reversed can be used.
Uses of Preorder
Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expression on of an expression tree.
Uses of Postorder
Postorder traversal is used to delete the tree. Please see the question for deletion of tree for details. Postorder traversal is also useful to get the postfix expression of an expression tree
Answer:
the Postorder Traversal is :DFEBGLUKHCA
Explanation:
An InOrder traversal, the nodes are traversed according to the following sequence :
- Left child will always go to it first.
- After it visits the left sub-tree, visit the currently given node.
- After visiting the node, move to its right sub-tree.
preorder of the binary tree is ABDEFCGHULK
inorder traversal of the binary tree is DBFEAGCLUHK
n a Preorder sequence, the leftmost element is the root of the tree. So we know ‘A’ is the root for given sequences. By searching ‘A’ in the Inorder sequence, we can find out all elements on the left side of ‘A’ is in the left subtree and elements on right in the right subtree. So we know the below structure now.
A
/ \
/ \
DBFE GCLUHK
We recursively follow the above steps and get the following tree.
A
/ \
/ \
B C
/ \ / \
/ \ / \
D FE G LUHK
A
/ \
/ \
B C
/ \ / \
/ \ / \
D E G H
/ / \
F U K
/
L
- The post order traversal technique follows the Left Right Root policy.
- Hence : the Postorder Traversal is :DFEBGLUKHCA