Page 112 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS
P. 112
Unit 5: Trees
Different order path in Figure 5.10 are: Notes
Inorder : a + b * c + d * e
postorder: abc*+de*+
Given an order of traversal of a tree it is possible to construct a tree.
Example: Consider the following order: Inorder = DBEAC
We can construct the binary trees shown below in figure using this order of traversal:
A
B C
D E C
A
E
B
D
E
B C
D A
Binary Trees Constructed using given Inorder
Therefore we conclude that given only one order of traversal of a tree it is possible to construct
a number of binary trees, a unique binary tree is not possible to be constructed. For construction
of a unique binary tree we require two orders in which one has to be inorder, the other can be
preorder or postorder.
Example: Consider the following orders:
lnorder = DBEAC
Postorder = DEBCA
We can construct a unique binary tree shown in Figure using these orders of traversal.
LOVELY PROFESSIONAL UNIVERSITY 107
