Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 🥳
1.1.
Problem Statement 🧾
1.2.
Sample Examples
2.
Approach 🧑‍💻
2.1.
Implementation in C++
2.1.1.
Time Complexity ⌛
2.1.2.
Space Complexity 🚀  
3.
Frequently Asked Questions
3.1.
What is a binary search tree?
3.2.
How many nodes are there in a complete binary tree?
3.3.
What is the level order traversal?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Node with minimum value in a BST

Author Harsh
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

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.

Question Title

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

input

 

Output

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;
}

 

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a binary search tree?

A binary search tree is a type of binary tree in which all of the nodes left to the root node have values less than the root node and all of the nodes right to the root node have values greater than the root node.
 

How many nodes are there in a complete binary tree?

If n is the total number of nodes, and h is the height of the tree then, total number of nodes in the complete binary tree is 2^h – 1.
 

What is the level order traversal?

It is a tree traversal in which each node is visited one level at a time. It can be explained as a breadth-first tree traversal.

Conclusion

In this article, we have extensively discussed a coding problem in which we have to find the node with the minimum value in binary search tree. We have seen a simple yet optimal solution to solve the problem.
 

If you think this blog has helped you enhance your knowledge about the above question, and if you would like to learn more, check out our articles 

and many more on our website.

Visit our website to read more such blogs. Make sure that you enroll in the courses provided by us, take mock tests and solve problems available and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help fellow ninjas grow.

Please upvote our blog to help other ninjas grow.

Happy Learning!

Previous article
Reverse a path in BST using queue
Next article
BST to a Tree with sum of all smaller keys
Live masterclass