Find the Maximum Value in a Binary Search Tree - Algorithm and Code Examples

Problem Statement❯

You are given the root of a Binary Search Tree (BST). Your task is to find and return the maximum value present in the tree. If the tree is empty, return null or any equivalent value indicating the tree has no nodes.

Examples❯

Input Tree	Max Value	Description
[20, 10, 30, 5, 15, 25, 35]	35	The maximum value in a BST is the rightmost node, which is 35 here.
[8, 4, 10, null, null, 9, 12]	12	Rightmost node in the BST is 12, which is the maximum.
[5, 3, null, 1]	5	No right subtree exists. Root 5 is the maximum.
[50, 30, 70, 20, 40, 60, 80]	80	Rightmost node of the BST is 80, so it is the maximum value.
[42]	42	Single-node tree. The only node is also the maximum.
[]	undefined	Empty tree has no elements, so no maximum value.

Visualization Player

Solution❯

Understanding the Problem

In a Binary Search Tree (BST), every node follows a specific rule: the left child contains values less than the node, and the right child contains values greater than the node. This structure helps us find the maximum value efficiently — we just need to follow the right children because the maximum value is always located at the rightmost node of the BST.

Let’s explore this idea with a detailed example and then walk through edge cases that a beginner should be aware of.

Step-by-Step Solution with Example

Step 1: Start at the Root

We begin at the root node of the BST. For example, consider the tree:


        4
       /       2   6
     /  /     1  3 5  7

The root is 4. Since we are looking for the maximum, we move to the right child.

Step 2: Keep Moving Right

From node 4, we move to 6. Then from 6, we move to 7. Node 7 has no right child, which means it is the rightmost node.

Step 3: Return the Node

Since 7 has no right child, we return 7 as the maximum value in the BST.

Step 4: Code Summary

The logic in code looks like this (pseudo-code):


function findMax(node):
    if node is null:
        return null
    while node.right is not null:
        node = node.right
    return node.value

Edge Cases

Case 1: Tree has only one node

If the tree has a single node, such as [10], that node is both the minimum and the maximum. Since there is no right child, we return 10 directly.

Case 2: Tree is empty

If the input tree is empty, there’s no value to return. In such cases, we return null or None depending on the language used. This signals that the tree has no nodes.

Case 3: Right-skewed tree

In a tree like [15, 10, 20, null, null, 18, 25], the maximum path is:


        15
                     20
                           25

We follow the path 15 → 20 → 25, and since 25 has no right child, it’s the maximum value.

Case 4: Tree with missing left children

Even if some left children are missing, it doesn't affect our search for the maximum — we ignore the left side completely. We only care about the rightmost path.

Finally

The beauty of a Binary Search Tree lies in its structure, which allows efficient search operations. To find the maximum value, we only need to traverse the right child nodes until we can go no further. For beginners, remember this simple rule: keep going right until you can't. And don’t forget to check for edge cases like empty trees or single-node trees for a robust solution.

Algorithm Steps❯

Given a binary search tree, if the tree is empty, return null or an appropriate value.
Initialize a variable current with the root node.
While current.right is not null, set current to current.right.
Once current.right is null, the current node holds the maximum value in the BST.
Return current.val as the maximum value.

Code

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int findMax(TreeNode* root) {
    if (root == NULL) return -1;
    TreeNode* current = root;
    while (current->right != NULL) {
        current = current->right;
    }
    return current->val;
}

int main() {
    TreeNode* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);
    root->right->right = createNode(20);

    printf("Max value: %d\n", findMax(root));
    return 0;
}

⬅ Previous TopicFind the Minimum Value in a Binary Search Tree

Next Topic ⮕Find the Inorder Successor in a Binary Search Tree

Comments

Loading comments...