Find the Minimum Value in a BST - Algorithm, Visualization, Examples

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

Given a Binary Search Tree (BST), find the minimum value stored in the tree. In a BST, the left child of a node contains a value less than the node itself, and the right child contains a value greater. You need to return the smallest value among all the nodes. If the tree is empty, return null or an appropriate error/indicator.

Examples❯

Input Tree Minimum Value Description
[10, 5, 15, 2, 7, null, 20]
2 The minimum value is at the leftmost node of the BST: 2.
[25, 20, 36, 10, 22, 30, 40]
10 BST's minimum is the leftmost node from the root: 10.
[50, 30, 70, 20, 40, 60, 80]
20 Smallest element in this BST is at the far left leaf: 20.
[8, null, 10, null, 12]
8 There is no left subtree, so the root itself is the minimum.
[100]
100 Single node tree, so root is also the minimum.
[] None Empty tree has no nodes; hence, no minimum exists.

Visualization Player

Solution❯

Case 1: Normal BST with multiple nodes

In a regular Binary Search Tree, the smallest value will always be found by continuously traversing to the left child until there are no more left children. For instance, in a BST like this:

          10
         /  \
        5   15
       /
      2

We start at 10, then go to 5, then finally reach 2, which has no left child. So 2 is the minimum.

Case 2: Left-skewed Tree

If the tree is skewed to the left (i.e., each node only has a left child), the minimum is the deepest node on the left. For example:

        20
       /
      10
      /
     5
    /
    3

Starting from 20, we go left repeatedly until we hit 3, which has no left child. This is the smallest value.

Case 3: Tree with a single node

In a single-node BST, like:

        42

There are no children at all. The root is the only node, so it is the minimum.

Case 4: Empty Tree

If the tree has no nodes at all (i.e., it’s null or []), there is no value to return. Depending on the language, you might return null, None, or raise an exception. This should be handled explicitly in code to avoid runtime errors.

Algorithm Steps❯

  1. Start at the root node of the BST.
  2. If the tree is empty, return an error or null.
  3. Iteratively traverse to the left child while it exists.
  4. When a node with no left child is reached, that node contains the minimum value.
  5. Return the value of this node.

Code

Python
Java
JavaScript
C
C++
C#
Go
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findMin(root):
    if not root:
        return None
    while root.left:
        root = root.left
    return root.val

if __name__ == '__main__':
    # Construct BST:
    #         5
    #        / \
    #       3   7
    #      / \  / \
    #     2  4 6   8
    root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(7, TreeNode(6), TreeNode(8)))
    print(findMin(root))