Using the BSTNode class defined in Exercise $3,$ implement the following member function of class BST$,$ which counts the number of nodes in the last level in the tree.

int count$\_$last$\_$level$()$ const;

Solution

Call compute$\_$heights$()$ and compute$\_$depths$().$

The depth of the last level is the height of the tree $($the height of the root$).$

Perform any traversal $($BFT$,$ in$-$order, post$-$order, pre$-$order$)$ and count nodes whose depth data member equals to the height of the root.