Minimum element in BST

Easy

0/40

Contributed by

33 upvotes

Problem statement

You are given a Binary Search Tree.

Find the minimum value in it.

Note:

All the values in the given binary search tree are unique.

Example:

Input : 6 4 7 2 5 N N

Output: 2

Explanation:
For the given input BST is:

      6
     / \
   4    7
  / \
 2   5

Minimum value in this tree is ‘2’.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains a string ‘T’ such that values in the string are in level order traversal of the tree, numbers denote the value of a node and character ‘N’ denotes a ‘NULL’ child. 

For example, for the given BST :

        4
      /   \
     2     5
    / \   / \
   1   3 N   N

Where N represents null child.

Input looks like following:
4 2 5 1 3 N N

Output Format:

Return the node with the minimum value. If tree is empty, return -1.

Note:

You don’t need to print anything, it has already been taken care of, just complete the given function.

Sample Input 1:

8 5 N 3 6

Sample Output 1:

Explanation of sample output 1:

BST for the given input looks like following:
    8
   / 
  5
 / \
3   6 
Thus the minimum value in this BST is ‘3’.

Sample Input 2:

5 3 6 2 4 N N

Sample Output 2:

Expected Time Complexity:

Try to do this in O(n), where 'n' is the number of nodes in the binary search tree.

Constraints:

0 <= ‘n’ <= 10^5
Time Limit: 1 sec

Where 'n' is the number of nodes in the binary tree.

Console