Solution: Find Minimum Value in Binary Search Tree
Let’s solve the Find Minimum Value in Binary Search Tree problem.
Statement
Given the root
node of a binary search tree (BST), find and return the minimum value present in the BST.
Constraints:
Let n
be the number of nodes in a binary search tree.
Solution 1: Iterative approach
The essence of the algorithm lies in the property of a BST, where the left subtree of a node contains values smaller than the node's value. Therefore, by traversing always to the left child, the algorithm guarantees that it reaches the minimum value node in the BST.
The steps of the algorithm are given below:
If the
root
is NULL, return NULL to indicate that the tree is empty.Initialize a
current
pointer to theroot
.Start traversing the tree using
current
untilcurrent
has a left child (i.e.,current->left
is not NULL).While traversing the tree, update
current
to be its left child:current = current->left
. This step effectively moves down the left side of the tree until reaching a leaf node (a node without a left child).When the loop exits (because
current->left
is NULL),current
points to the leftmost node in the tree. This leftmost node is the node with the minimum value in the BST.
Let’s look at the illustration below to better understand the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.