Question

Q1. Given (a b* (c d* e)) draw the corresponding tree. * indicates non-leaves.

Indicate the balance factor and height for each non-leaf.[3]

Q2. To compute and store the height and balance factor of each vertex, what traversal order would be ideal? Why?[2]

Answer 1

Q1.

BalanceFactor = height(left-sutree) − height(right-sutree)

we used same formula in tree.

  

Q2.

As According to the formula of BalanceFactor we need height of both left and right subtree value inorder to calculate balance factor for a node . So we will prefer to use a bottom up approach instead of top down approach.

And stack or recursion is best way to achieve bottom up approach. we will use depth first search here instead of breadth first search beacuse we need to calculate height of child node first to calculate height and balance factor of a node.