Log inSign up
easyGeeksforGeeksNot Started

Maximum 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 maximum element in the BST.

Return the value of the node with the maximum 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 extremum values in a BST.
  • Contrast O(H) BST lookup with O(N) generic binary tree traversal.
  • Implement the O(1) space right-spine descent.

Pattern Recognition Trigger

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

Signals to Look For:

  • Find maximum value in Binary Search Tree.
  • Monotonic rightward path.
  • Extreme value lookup in BST.

Algorithmic Decision Tree:

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

Connected Patterns:

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

1. Full Tree Traversal (Unordered Max Search)

Intuition

Traverse every node in the tree using preorder or inorder traversal. Maintain a variable maxVal. For each visited node, update maxVal = max(maxVal, curr.data). Returns the maximum 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 maximum.
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& maxVal) {
14 if (!root) return;
15 maxVal = std::max(maxVal, root->data);
16 dfs(root->left, maxVal);
17 dfs(root->right, maxVal);
18 }
19public:
20 int maxValue(Node* root) {
21 if (!root) return -1;
22 int maxVal = INT_MIN;
23 dfs(root, maxVal);
24 return maxVal;
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->right->right = new Node(25);
33
34 Solution sol;
35 std::cout << "Max: " << sol.maxValue(root) << std::endl;
36 return 0;
37}

Time & Space Complexity

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

2. Recursive Right Spine Traversal

Intuition

1. Base case: if (root.right == null) return root.data. 2. Recurse right: return maxValue(root.right).

When to apply: When writing concise recursive solutions.

Algorithm

  1. Recurse into root.right until root.right 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 maxValue(Node* root) {
13 if (!root) return -1;
14 if (!root->right) return root->data;
15 return maxValue(root->right);
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->right->right = new Node(25);
24
25 Solution sol;
26 std::cout << "Max: " << sol.maxValue(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 Rightmost Node Traversal

Intuition

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

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

Algorithm

  1. Follow right pointers in a simple while loop until reaching the rightmost node.

Right-Spine Maximum Traversal Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
In a BST, larger values only lie to the right
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.right exists (22). Move curr = 22.
Decision / next transition
1
Why this step matters

In a BST, larger values only lie to the right.

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 maxValue(Node* root) {
13 if (!root) return -1;
14 Node* curr = root;
15 while (curr->right) {
16 curr = curr->right;
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->right->right = new Node(25);
27
28 Solution sol;
29 std::cout << "Max: " << sol.maxValue(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 Max Search)O(N)O(H) recursion stack spaceVisit every node in the tree using DFS and maintain the global maximum.O(N)
2.Recursive Right Spine TraversalO(H) where H is tree heightO(H) recursion stack spaceRecurse into root.right until root.right is null; return root.data.O(H) where H is tree height
3.Iterative Rightmost Node TraversalOptimalO(H) where H is tree heightO(1) auxiliary spaceFollow right pointers in a simple while loop until reaching the rightmost node.O(H) where H is tree height

Common Pitfalls & Crucial Edge Cases

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

Causes curr to become null, requiring tracking prev.

Checking both subtrees

Wastes time visiting the left 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 right child; returns root value in O(1).
  • Left-skewed tree — Root has no right child; returns root value in O(1).
  • Right-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.right) curr = curr.right loop.
  2. Point out that the maximum element is not necessarily a leaf (it may have a left child).
  3. Mention that while worst case is O(H), on a left-skewed tree it is O(1)!

Quick Comprehension Check

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

1.Can the maximum element in a BST ever have a right child?

2.Can the maximum element in a BST have a left child?

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

Back to DSA Sheet