Step $1$: Calculate the height of the binary search tree.

Binary search trees containing the same data items can vary widely in shape depending on the order in which the data items were inserted into trees. One measurement of a tree's shape is its height. This statistic is significant because the amount of time that it can take to search for an item in a binary search tree is a function of the height of the tree.

The height of any node in a tree is the number of edges $($links or steps$)$ on the longest path from that node to any leaf node under it$.$ A leaf node has a height of $0,$ as does a tree with only one node $($the root$).$ An empty tree has no defined height$$for our purposes we will use the sentinel value $-1.$

You can compute the height of a binary search tree using a post$-$order traversal and the following recursive definition of height for a tree rooted at a given node p$.$