Node with minimum value in a BST

Introduction 🥳

A binary tree is a binary search tree if it holds the following properties:- left subtree have all nodes smaller than the root node, right subtree has all the nodes greater than the root node, and both left and right subtree are binary search trees themselves.

For example, The tree shown in the below image is a binary search tree as all of the items left to the root node are smaller and all of the items right to the root node are greater. This property holds for all of the nodes present in the binary tree.

In this blog, we will discuss a coding problem related to binary search trees.

Problem Statement 🧾

Ninja has given you a binary search tree. Your task is to find the node with the minimum value.

Sample Examples

Input

Output

Explanation

Node with the minimum value in the above binary search tree is 5.

Approach 🧑‍💻

Simply iterate recursively from root to left until left is NULL. The node with the lowest value is the one whose left is NULL. This is directly because of the property of BST mentioned above.

Algorithm
MIN_NODE(ROOT):
    if ROOT is null:
        return null
    if ROOT->left is null:
        return ROOT    
return MIN_NODE(ROOT->Left)

Implementation in C++

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


class Node
{
public:
    int data;
    Node *left, *right;
    Node(int val){
        data = val;
        left = right = nullptr;
    }
};

// function to find the the node with minimum value
Node *minNode(Node *root){
    if(root == nullptr) return nullptr;    
    if(root->left == nullptr) return root;
    return minNode(root->left);
}

Node *insertData(Node *root, int data) {

    // tree is empty, return new node
    if (root == nullptr) return new Node(data);

    // recurr the tree to find the position where
    // data needs to be inserted
    if (data < root->data) root->left = insertData(root->left, data);
    else if (data > root->data) root->right = insertData(root->right, data);

    // return the root node
    return root;
}

int main(){

    // creating binary search tree
    Node *root = nullptr;
    root = insertData(root, 20);
    insertData(root, 10);
    insertData(root, 5);
    insertData(root, 12);
    insertData(root, 40);
    insertData(root, 25);
    insertData(root, 45);

    Node* min = minNode(root);

    cout << "Minimum value in BST: " << min->data << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Minimum value in BST: 5

Time Complexity ⌛

The time complexity of the above approach is O(N), where N is the numberimage widget of nodes in the binary search tree. This is when the binary search tree is not balanced (skewed). However, if it is given that the BST is balanced, then the time complexity would be O(logN), where N is again the number of nodes in the tree.
 

Space Complexity 🚀  

The space complexity of the above approach is O(N), where N is the number of nodes in the tree. It is because of the size of the recursion stack used in the implementation.
Check out this problem - Largest BST In Binary Tree