ProgramGuru

Find the Minimum Value in a Binary Search Tree

Problem and examples

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.

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.

Explore Find the Minimum Value in a BST

Load an example or enter your own input. Use the player controls to follow each change.

Understanding the Problem

We are given a Binary Search Tree (BST), and we are asked to find the minimum value present in it. A Binary Search Tree is a binary tree where for each node: - All values in the left subtree are less than the node. - All values in the right subtree are greater than the node.

The minimum value in a BST will always be the leftmost node because smaller values are always inserted to the left. Let's understand this with a clear example and then walk through the solution step by step.

Step-by-Step Solution with Example

Step 1: Look at the Root

Start with the root node of the BST. This is where our search for the minimum value begins. Let's consider the following example tree:

    10
   /    5    15
 /
2

The root node here is 10.

Step 2: Move to the Left Child

According to BST rules, the left child will always have a smaller value. So from 10, we move left to 5.

Step 3: Keep Going Left

From 5, we again move left to 2, because we are looking for the smallest value. If 2 had a left child, we would continue left. But 2 has no left child.

Step 4: Stop at the Leftmost Node

Since 2 has no further left children, it is the minimum value in this BST. This logic applies to all BSTs — the leftmost node is always the smallest.

Edge Cases

Case 1: Left-skewed Tree

    20
   /
  10
 /
5
/
3

In this case, we keep moving left from 20 → 10 → 5 → 3. The node 3 has no left child, so it is the minimum value.

Case 2: Single-node Tree

    42

There are no left or right children. The root itself is the minimum value.

Case 3: Empty Tree

If the BST is empty (i.e., root is null), there is no minimum value. Your function should handle this case safely by either:

  • Returning null or None,
  • Throwing an appropriate exception, or
  • Returning a message that the tree is empty.

Finally

Finding the minimum in a BST is a very intuitive process — just keep going left until you can't go any further. This works because of the BST property that all smaller elements lie to the left. Make sure your code handles edge cases like empty trees and single-node trees, especially in interviews or production-level code. A safe, defensive approach leads to more reliable software.

  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.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int findMin(TreeNode* root) {
    if (root == NULL) {
        printf("Tree is empty\n");
        exit(1);
    }
    while (root->left != NULL) {
        root = root->left;
    }
    return root->val;
}

int main() {
    TreeNode* root = createNode(5);
    root->left = createNode(3);
    root->right = createNode(7);
    root->left->left = createNode(2);
    root->left->right = createNode(4);
    root->right->left = createNode(6);
    root->right->right = createNode(8);
    printf("%d\n", findMin(root));
    return 0;
}

C++ implementation

#include <iostream>
#include <stdexcept>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

int findMin(TreeNode* root) {
    if (!root) {
        throw runtime_error("Tree is empty");
    }
    while (root->left) {
        root = root->left;
    }
    return root->val;
}

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(8);
    cout << findMin(root) << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

if __name__ == '__main__':
    root = TreeNode(5,
            TreeNode(3, TreeNode(2), TreeNode(4)),
            TreeNode(7, TreeNode(6), TreeNode(8)))
    print(find_min(root))

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class FindMinInBST {
    public static int findMin(TreeNode root) {
        if (root == null) {
            throw new IllegalArgumentException("Tree is empty");
        }
        while (root.left != null) {
            root = root.left;
        }
        return root.val;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(8);
        System.out.println(findMin(root));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findMin(root) {
    if (!root) return null;
    while (root.left) {
        root = root.left;
    }
    return root.val;
}

const root = new TreeNode(5,
    new TreeNode(3, new TreeNode(2), new TreeNode(4)),
    new TreeNode(7, new TreeNode(6), new TreeNode(8))
);
console.log(findMin(root));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func findMin(root *TreeNode) int {
    if root == nil {
        panic("Tree is empty")
    }
    for root.left != nil {
        root = root.left
    }
    return root.val
}

func main() {
    root := &TreeNode{5,
        &TreeNode{3, &TreeNode{2, nil, nil}, &TreeNode{4, nil, nil}},
        &TreeNode{7, &TreeNode{6, nil, nil}, &TreeNode{8, nil, nil}},
    }
    fmt.Println(findMin(root))
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn find_min(mut root: &Option<Box<TreeNode>>) -> i32 {
    if root.is_none() {
        panic!("Tree is empty");
    }
    while let Some(ref node) = root {
        if node.left.is_none() {
            return node.val;
        }
        root = &node.left;
    }
    unreachable!()
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 5,
        left: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode::new(2))),
            right: Some(Box::new(TreeNode::new(4))),
        })),
        right: Some(Box::new(TreeNode {
            val: 7,
            left: Some(Box::new(TreeNode::new(6))),
            right: Some(Box::new(TreeNode::new(8))),
        })),
    }));

    println!("{}", find_min(&root));
}

Kotlin implementation

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun findMin(root: TreeNode?): Int {
    var current = root ?: throw IllegalArgumentException("Tree is empty")
    while (current.left != null) {
        current = current.left!!
    }
    return current.value
}

fun main() {
    val root = TreeNode(5).apply {
        left = TreeNode(3).apply {
            left = TreeNode(2)
            right = TreeNode(4)
        }
        right = TreeNode(7).apply {
            left = TreeNode(6)
            right = TreeNode(8)
        }
    }
    println(findMin(root))
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

func findMin(_ root: TreeNode?) -> Int {
    guard var current = root else {
        fatalError("Tree is empty")
    }
    while let next = current.left {
        current = next
    }
    return current.val
}

let root = TreeNode(5,
            TreeNode(3, TreeNode(2), TreeNode(4)),
            TreeNode(7, TreeNode(6), TreeNode(8)))
print(findMin(root))

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findMin(root: TreeNode | null): number | null {
    if (!root) return null;
    while (root.left) {
        root = root.left;
    }
    return root.val;
}

const root = new TreeNode(5,
    new TreeNode(3, new TreeNode(2), new TreeNode(4)),
    new TreeNode(7, new TreeNode(6), new TreeNode(8))
);
console.log(findMin(root));