How to find minimum value in a Binary Search Tree (BST)

The naive approach, visit all nodes, and compare a value in each node. A better approach is to use the definition of a binary search tree.

A Binary Search Tree (BST) is a binary tree where each node has a key and meet the following requirements:

• The left subtree of a node contains nodes with keys smaller then the node's key
• The right subtree of a node contains nodes with keys larger then the node's key
• The left and right subtrees are binary search trees

In other words, the most leftist node in a BST has a minimum value.

Examples

Let's see a couple of BST examples. As we see the leftmost node has a minimum value and the leftmost node it's a left node without a left child.

 

 

 

In this example, the root node has the minimum value.

Algorithm

The answer to the question "How to find minimum value in a Binary Search Tree (BST)":

• always go to the left until finding a node without a left child. This node will have minimum value in a BST.

The last question we need to answer before start writing code. What should the algorithm do if a BST is empty? For simplicity, let's return -1 if a BST is empty.

Note: ask a question on your interview. Is it ok to return a -1 if BST is empty? BST can store not only positive but negative values as well.

    public int MinValue(TreeNode root)
    {
        if (root == null)
        {
            return -1;
        }

        TreeNode node = root;
        while (node.Left != null)
        {
            node = node.Left;
        }

        return node.Value;
    }