Height of binary search tree
After discussing BST and basic operations on BST, let us workout some other problems which involve some attributes of binary search tree. One such attribute is height of BST. What is Height of binary search tree or binary tree?
Height of binary search tree is maximum of distances between root and leaf nodes of tree. In other words, it’s 1 + maximum number of edges from root to any of the leaf node. For example, height of tree given below is 3.
where as height of this tree is 4.
Usually, there is some confusion between depth of a node and height of tree. Depth of a node is property of a node and is distance between that node and root. However, height of tree is tree property and defined as maximum depth of any node of tree. See how they are related; height of tree = maximum depth of a node in tree.
Calculate height of binary search tree
Height of tree is calculated bottom up, that means, we calculate height of leaf nodes first and then add that up to their parent, then parent of parent and so on till we reach root node.
Now, any node in BST can have two children. Question is whose height should we consider to add to get it’s parent’s height? As per definition, height is maximum distance of leaf node from root, hence, we should take the value which is maximum and push it up to parent.
This problem is classic case of applying divide and conquer and greedy algorithms. Divide and conquer as height of a node is decided by heights of it’s subtree, so we divide the problem till we don’t have leaf node and then solve simple problem and go up.
Greedy because at each node we select the maximum height of left or right subtree.
1. If tree is empty, return 0. 2. For each node, 2.1 If it has left child, find height of left subtree (lheight) 2.2 If it has right child, find height of right subtree (rheight) 2.3 Return 1 + maximum of lheight and rheight.
Implementation is quite simple using recursion.
Example how height of tree is being calculate in algorithm
Complexity of algorithm to find height of binary search tree is O(N) as we will visit each of node at least once.
Please share if something is wrong or missing. Sharing is caring.