Find minimum in binary search tree
We discussed binary search tree and it’s properties. Properties of binary search trees are: 1. Left child node is less than its parent node. 2. Right child node is greater than its parent node. These properties hold good for all subtrees in a BST. Today, let’s discuss a problem which uses these properties of BST, and the problem is : Find minimum in binary search tree. On the same lines, it can also be asked to find maximum in a binary search tree. For example in given binary search tree, minimum is 15 and maximum is 45
Both problems can be handled in similar way, only difference is the part of tree which is traversed.
As per the property of BST, all nodes on left side of a given node are smaller and all nodes on right side are greater than it. How to use this information to find minimum in binary search tree? Minimum will have no children on left subtree of it. Why? Because, if left subtree of current node has children, they will be smaller than current node and hence it cannot be minimum. Hence, minimum will be left most node of binary search tree. While finding minimum, we never go to right child of any node in path till left most node.
Minimum in binary search tree implementation
Implementation wise, solution to find minimum in binary search tree can be implemented in iterative as well as recursive way.
Continuing on the same lines, what will be the maximum in binary search tree? It should be rightmost node in BST.
Maximum in binary search tree implementation
Complexity of algorithm to find minimum in binary search tree is O(N) in case tree is completely skewed and O(log N) in balanced binary search tree. Complexity remains same to find maximum in binary search tree.
Please share if there is something wrong or missing. If you are interested in contributing to website, please write to us.