Question

M = [4,3,7,6,5,2,4,1,0,7]

Construct a binary search tree for M. Then traverse it (post order)

Answer 1

When inserting in a BST(Binary search tree), insertion is always performed at the leaf of the tree. Each time a new element is to be inserted, it is compared to the root node, if it is greater than the root then it goes to the right subtree otherwise to the left subtree. Then the comparision is made to the root of the next sub tree and so on until the insertion is to be done at the leaf node.

Constructing a BST for M:

Insert 4:

Insert 3:

Since 3 < 4, it goes to the left.

Insert 7:

Since 7>=4, it goes to the right:

Insert 6:

6>=4 so it goes to the right subtree. 6<7 so it goes to the left of 7. Similarly each element is inserted into the tree.

Insert 5:

Insert 2:

Insert 4:

Insert 1:

Insert 0:

Insert 7:

This is the final tree that will be generated after all the values have been generated.

POST ORDER TRAVERSAL:

The post order travaersal follows the order LEFT,RIGHT,ROOT in a recursive fashion. So, the post order traversal of the above tree is:

0,1,2,3,4,5,6,7,7,4