Home » Technical Interview Questions » Tree Interview Questions » Find the node with minimum value in a Binary Search Tree

Find the node with minimum value in a Binary Search Tree


Reading Time - 5 mins

Given a Binary Search Tree, write an algorithm to find the node with the minimum value in a given binary search tree.

Example

Input

Find the node with minimum value in a Binary Search Tree

Output
5

Naive Approach

A simple approach is to do a tree traversal and find the node with the minimum value among all the nodes. This method is not only valid for a binary search tree, but also for any general tree.
Suppose we do a level-order traversal to find the minimum value.

  1. If the root is null, there is no minimum value, return infinity.
  2. Initialize the minimum value is infinite.
  3. Create a queue and push the root to it. Repeat step 4 while the queue is not empty.
  4. Remove a node from the queue, update the minimum value as a minimum of minimum value, and the current node’s value. Push the children of the current node to the queue.
  5. Return minimum value.

Time Complexity = O(n)
Space Complexity = O(n)
where n is the total number of nodes in the given BST.

JAVA Code for Find the node with a minimum value

import java.util.LinkedList;
import java.util.Queue;

public class FindTheNodeWithMinimumValueInABinarySearchTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int minValue(Node root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }

        // initialize min as infinite
        int min = Integer.MAX_VALUE;

        // do a level order traversal of the tree
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            // update minimum
            min = Math.min(min, curr.data);

            // add children of curr to queue
            if (curr.left != null)
                queue.add(curr.left);
            if (curr.right != null)
                queue.add(curr.right);
        }

        return min;
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(25);
        root.left = new Node(18);
        root.right = new Node(30);
        root.left.left = new Node(5);
        root.right.left = new Node(27);
        root.right.right = new Node(33);
        root.left.left.right = new Node(11);

        System.out.println(minValue(root));
    }
}
5

C++ Code for Find the node with a minimum value

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

int minValue(Node *root) {
    if (root == NULL) {
        return INT_MAX;
    }
    
    // initialize min as infinite
    int min = INT_MAX;
    
    // do a level order traversal of the tree
    queue<Node*> q;
    q.push(root);
    
    while (!q.empty()) {
        Node *curr = q.front();
        q.pop();
        
        // update minimum
        min = std::min(min, curr->data);
        
        // add children of curr to queue
        if (curr->left != NULL)
            q.push(curr->left);
        if (curr->right != NULL)
            q.push(curr->right);
    }
    
    return min;
}

int main() {
    // Example Tree
    Node *root = new Node(25);
    root->left = new Node(18);
    root->right = new Node(30);
    root->left->left = new Node(5);
    root->right->left = new Node(27);
    root->right->right = new Node(33);
    root->left->left->right = new Node(11);

    cout<<minValue(root)<<endl;
    
    return 0;
}
5

Optimal Approach

The given binary tree is a Binary Search Tree. Binary Search Tree has a special property that all the nodes less than a node are present in its left sub-tree and all the nodes greater than this node are present in the right sub-tree.
Using this property, we can say that the node with minimum value is present as the leftmost node in the tree.

  1. If the root is null, there is no minimum, return infinite.
  2. Else initialize temp as root. Repeat step 3 while temp’s left node is not null.
  3. Make temp equals temp’s left.
  4. At this point, temp is pointing to the leftmost node, that is, the node with minimum value. Return temp’s data.
READ  Interval Tree

Time Complexity = O(h)
Space Complexity = O(1)
where h is the height of given binary search tree, in worst case h equals to n(number of nodes).

JAVA Code for Find the node with a minimum value

public class FindTheNodeWithMinimumValueInABinarySearchTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int minValue(Node root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }

        // initialize temp as root
        Node temp = root;
        // go to the left most node
        while (temp.left != null) {
            temp = temp.left;
        }

        // return value of left most node
        return temp.data;
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(25);
        root.left = new Node(18);
        root.right = new Node(30);
        root.left.left = new Node(5);
        root.right.left = new Node(27);
        root.right.right = new Node(33);
        root.left.left.right = new Node(11);

        System.out.println(minValue(root));
    }
}
5

C++ Code for Find the node with a minimum value

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

int minValue(Node *root) {
    if (root == NULL) {
        return INT_MAX;
    }
    
    // initialize temp as root
    Node *temp = root;
    // go to the left most node
    while (temp->left != NULL) {
        temp = temp->left;
    }
    
    // return value of left most node
    return temp->data;
}

int main() {
    // Example Tree
    Node *root = new Node(25);
    root->left = new Node(18);
    root->right = new Node(30);
    root->left->left = new Node(5);
    root->right->left = new Node(27);
    root->right->right = new Node(33);
    root->left->left->right = new Node(11);

    cout<<minValue(root)<<endl;
    
    return 0;
}
5

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions