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

**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__