Log inSign up
easyGeeksforGeeksNot Started

Minimum Element in BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a Binary Search Tree (BST), find the minimum element in the BST.

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

Constraints:

  • 0 <= Number of nodes <= 105
  • 1 <= Node.data <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the structural placement of the minimum key in a BST.
  • Contrast O(H) spine descent with O(N) full tree traversal.
  • Implement the O(1) space iterative solution.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find minimum element in BST.
  • Leftmost spine traversal.
  • Extreme minimum lookup in BST.

Algorithmic Decision Tree:

  • Start at root: while (curr.left) curr = curr.left.
  • Return curr.data.

Connected Patterns:

Maximum Element in BSTInorder Successor in BSTSearch in a Binary Search Tree

1. Full Tree Traversal (Unordered Min Search)

Intuition

Traverse every node in the tree using preorder or inorder traversal. Maintain a variable minVal. For each visited node, update minVal = min(minVal, curr.data). Returns the minimum element after visiting all N nodes in O(N) time.

When to apply: Baseline comparison for generic binary trees where BST invariants do not apply.

Algorithm

  1. Visit every node in the tree using DFS and maintain the global minimum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <algorithm>
3#include <climits>
4
5struct Node {
6 int data;
7 Node* left;
8 Node* right;
9 Node(int val) : data(val), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13 void dfs(Node* root, int& minVal) {
14 if (!root) return;
15 minVal = std::min(minVal, root->data);
16 dfs(root->left, minVal);
17 dfs(root->right, minVal);
18 }
19public:
20 int minValue(Node* root) {
21 if (!root) return -1;
22 int minVal = INT_MAX;
23 dfs(root, minVal);
24 return minVal;
25 }
26};
27
28int main() {
29 Node* root = new Node(20);
30 root->left = new Node(8);
31 root->right = new Node(22);
32 root->left->left = new Node(4);
33
34 Solution sol;
35 std::cout << "Min: " << sol.minValue(root) << std::endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack space

2. Recursive Left Spine Traversal

Intuition

1. Base case: if (root.left == null) return root.data. 2. Recurse left: return minValue(root.left).

When to apply: When writing concise recursive solutions.

Algorithm

  1. Recurse into root.left until root.left is null; return root.data.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct Node {
4 int data;
5 Node* left;
6 Node* right;
7 Node(int val) : data(val), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int minValue(Node* root) {
13 if (!root) return -1;
14 if (!root->left) return root->data;
15 return minValue(root->left);
16 }
17};
18
19int main() {
20 Node* root = new Node(20);
21 root->left = new Node(8);
22 root->right = new Node(22);
23 root->left->left = new Node(4);
24
25 Solution sol;
26 std::cout << "Min: " << sol.minValue(root) << std::endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(H) recursion stack space

3. Iterative Leftmost Node Traversal

Intuition

1. If root == null, return -1. 2. Set curr = root. 3. Loop while (curr.left != null) curr = curr.left. 4. Return curr.data. Takes O(H) time and strictly O(1) auxiliary space.

When to apply: Optimal in both time and space. Zero recursion overhead.

Algorithm

  1. Follow left pointers in a simple while loop until reaching the leftmost node.

Left-Spine Minimum Traversal Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
In a BST, smaller values only lie to the left
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
curr = 20. curr.left exists (8). Move curr = 8.
Decision / next transition
1
Why this step matters

In a BST, smaller values only lie to the left.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct Node {
4 int data;
5 Node* left;
6 Node* right;
7 Node(int val) : data(val), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 int minValue(Node* root) {
13 if (!root) return -1;
14 Node* curr = root;
15 while (curr->left) {
16 curr = curr->left;
17 }
18 return curr->data;
19 }
20};
21
22int main() {
23 Node* root = new Node(20);
24 root->left = new Node(8);
25 root->right = new Node(22);
26 root->left->left = new Node(4);
27
28 Solution sol;
29 std::cout << "Min: " << sol.minValue(root) << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(H) where H is tree height
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Full Tree Traversal (Unordered Min Search)O(N)O(H) recursion stack spaceVisit every node in the tree using DFS and maintain the global minimum.O(N)
2.Recursive Left Spine TraversalO(H) where H is tree heightO(H) recursion stack spaceRecurse into root.left until root.left is null; return root.data.O(H) where H is tree height
3.Iterative Leftmost Node TraversalOptimalO(H) where H is tree heightO(1) auxiliary spaceFollow left pointers in a simple while loop until reaching the leftmost node.O(H) where H is tree height

Common Pitfalls & Crucial Edge Cases

Checking `curr != null` instead of `curr.left != null`

Causes curr to become null, requiring tracking prev.

Checking both subtrees

Wastes time visiting the right subtree.

Forgetting null check on root

Leads to immediate crash on empty tree inputs.

Crucial Edge Cases to Validate:

  • Empty tree (`root == null`) — Returns -1.
  • Single node tree — Root has no left child; returns root value in O(1).
  • Right-skewed tree — Root has no left child; returns root value in O(1).
  • Left-skewed tree — Traverses all N nodes in O(N) time.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Keep it simple: Write the 4-line iterative while (curr.left) curr = curr.left loop.
  2. Point out that the minimum element is not necessarily a leaf (it may have a right child).
  3. Mention that while worst case is O(H), on a right-skewed tree it is O(1)!

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Can the minimum element in a BST ever have a left child?

2.Can the minimum element in a BST have a right child?

3.What is the worst-case time complexity of finding the minimum in a right-skewed BST?

Back to DSA Sheet