Solution: Find Minimum Value in Binary Search Tree

Let’s solve the Find Minimum Value in Binary Search Tree problem.

We'll cover the following

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.

  • 0≤0 \leq n ≤500\leq500

  • −104≤-10^4\leq Node.data ≤104\leq10^4

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:

  1. If the root is NULL, return NULL to indicate that the tree is empty.

  2. Initialize a current pointer to the root.

  3. Start traversing the tree using current until current has a left child (i.e., current.left is not NULL).

  4. 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).

  5. 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.