Node with minimum value in a Binary Search Tree

Question

I would like to find the most efficent way to check the node with minimum value in a Binary Search Tree. I'm not thinking to do it in a certain programming language right now, I would like just to think the most efficent algorithm.

What do you think about this:

procedure minBST(t)
if (t = NULL) then return; 
if (t -> left = NULL) then return  t -> inf;  
 *// if the left node is null, then in a BST the smallest value will be the root*
if (t -> left != NULL) then .... 
 *// I need to dig more in the left side until I get the last left node*

My question is how should I dig deeper until I get the last left node. Also I tried to explain the steps. Do you think that is the best way to do it?

What do you mean by efficient. Algorithmically, Verbosity of code, Memory Efficiency. Easiest is to visit every node store best on the way. See http://stackoverflow.com/questions/15306452/traversing-through-all-nodes-of-a-binary-tree-in-java. — Charles Beattie, Jan 14 '14 at 09:37
efficiency = smallest complexity. I already saw that example and don't help me to much. I need to understand how to go deep after I check the first left node. What and how I do it if I have 10 nodes let's say. — redhat01, Jan 14 '14 at 09:42
Can someone help me with this question? How can we prove that the smallest node in a binary search tree is obtained by recursively going left from the root? — Neel Sandell, Jun 06 '22 at 01:31

score 6 · Accepted Answer · answered Jan 14 '14 at 09:59

If you have a proper BST you can continue going down the left child:

     10
   /    \
  5      12
 / \    /  \
1   6  11  14

If a node does not have a left child (Null) you know the node you're currently in has the minimum value. The easiest approach is via recursion:

int minBST(TreeNode node)
{
  if (node->left == Null)
    return node->value;
  else
    return minBST(node->left);
}

To start the search simply call the function above with the root as node parameter. The tree above will have a code path as follows:

minBST(node with value 10) -> has left child -> minBST(node with value 5)
minBST(node with value 5) -> has left child -> minBST(node with value 1)
minBST(node with value 1) -> has no left child -> return 1

If your tree contains n nodes and is balanced (equal depth everywhere) this will take O(log_2 n) operations and is the fastest approach without additional bookkeeping. The fact that the tree is balanced is important to get the best performance, if you want to maintain your tree balanced have a look at red-black trees.

score 3 · Answer 2 · answered Jan 14 '14 at 09:44

3

The following code should do the job:

node* FindMin(node* n)
{
    if(n == NULL)
        return NULL;

    if(n->left == NULL)
        return n;

    while(n->left != NULL)
    {
        n = n->left;
    }

    return n;
}

The complexity is O(log(n)), that the best you can get assuming the tree is balanced.

answered Jan 14 '14 at 09:44

Uri Y

840
5
13

2

The second conditional, `if (n-> left == NULL)` is not required. If you remove it then the `while` loop is never entered and the function will correctly return `n`. – Jim Mischel Jan 14 '14 at 15:37

score 0 · Answer 3 · answered Aug 12 '20 at 13:43

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

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

        return node.Value;
    }

https://codestandard.net/articles/min-value-binary-search-tree

Node with minimum value in a Binary Search Tree

3 Answers3