Minimum Value of a Binary Search Tree

The problem statement is that you have to find the minimum value of a binary search tree.

We should know that Binary Search Tree, it is a tree with its node arrange in way that smaller value goes to left of parent node and larger value goes to right of parent node.

If we clearly see a Binary Search Tree then we will see that the smaller values are on left sides. So, if we apply a logic to get the last left node of the tree then we will get the minimum / smallest value of the tree.

Let’s try to find the solution with a example:
Input: "5 4 6 3 N N 7 1";
Output: 1

First, we have convert the string into a binary search tree, that we will do it using Queue. Then will traverse till last left node of the tree.

import java.util.Queue;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
class Node {
 int data;
 Node left, right;
 Node(int data) {
  this.data = data;
  left = null;
  right = null;
 }
}
class Tree {
static Node buildTree(String s) {
if (s.length() == 0 || s.charAt(0) == 'N') {
 return null;
}
String[] tV = s.split(" ");
Node root = new Node(Integer.parseInt(tV[0]));
Queue<Node> q = new LinkedList<>();
q.add(root);
int i = 1;
while (q.size() > 0 && i < tV.length) {
 Node currNode = q.peek();
 q.remove();
if (!tV[i].equals("N")) {
currNode.left = new Node(Integer.parseInt(tV[i]));
q.add(currNode.left);
}
i++;
if (i >= tV.length)
 break;
if (!tV[i].equals("N")) {
currNode.right = new Node(Integer.parseInt(tV[i]));
q.add(currNode.right);
}
i++;
}
return root;
}
static int minValue(Node node) {
Node currNode = node;
// in BST, all small values are on left node, so we are traversing till last
// left node
while (currNode.left != null) {
currNode = currNode.left;
}
return currNode.data;
}
}
class minValueOfBST {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
String s = br.readLine();
Node root = Tree.buildTree(s);
int minValue = Tree.minValue(root);
System.out.println(minValue);
}
}
}

This is a re-post of my original post on blogspot — https://santosh-yadaav.blogspot.com/2020/06/minimum-value-of-binary-search-tree.html