Find the Maximum Value in a Binary Search Tree

Problem and examples

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.

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.

Explore Find the Maximum Value in a Binary Search Tree

Load an example or enter your own input. Use the player controls to follow each change.

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.

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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

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

    cout << "Max value: " << findMax(root) << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_max(root):
    if not root:
        return None
    current = root
    while current.right:
        current = current.right
    return current.val

# Example usage
if __name__ == '__main__':
    root = TreeNode(10, TreeNode(5), TreeNode(15, None, TreeNode(20)))
    print("Max value:", find_max(root))

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class FindMaxInBST {
    public int findMax(TreeNode root) {
        if (root == null) return -1;
        TreeNode current = root;
        while (current.right != null) {
            current = current.right;
        }
        return current.val;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.right.right = new TreeNode(20);

        FindMaxInBST finder = new FindMaxInBST();
        System.out.println("Max value: " + finder.findMax(root));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findMax(root) {
    if (!root) return null;
    let current = root;
    while (current.right !== null) {
        current = current.right;
    }
    return current.val;
}

// Example usage
const root = new TreeNode(10, new TreeNode(5), new TreeNode(15, null, new TreeNode(20)));
console.log("Max value:", findMax(root));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func createNode(val int) *TreeNode {
    return &TreeNode{val: val}
}

func findMax(root *TreeNode) int {
    if root == nil {
        return -1
    }
    current := root
    for current.right != nil {
        current = current.right
    }
    return current.val
}

func main() {
    root := createNode(10)
    root.left = createNode(5)
    root.right = createNode(15)
    root.right.right = createNode(20)
    fmt.Println("Max value:", findMax(root))
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn find_max(mut root: &TreeNode) -> i32 {
    while let Some(ref right) = root.right {
        root = right;
    }
    root.val
}

fn main() {
    let root = TreeNode {
        val: 10,
        left: Some(Box::new(TreeNode::new(5))),
        right: Some(Box::new(TreeNode {
            val: 15,
            left: None,
            right: Some(Box::new(TreeNode::new(20))),
        })),
    };
    println!("Max value: {}", find_max(&root));
}

Kotlin implementation

class TreeNode(var val: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun findMax(root: TreeNode?): Int {
    var current = root ?: return -1
    while (current.right != null) {
        current = current.right!!
    }
    return current.val
}

fun main() {
    val root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(15)
    root.right!!.right = TreeNode(20)

    println("Max value: ${findMax(root)}")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func findMax(_ root: TreeNode?) -> Int? {
    guard var current = root else { return nil }
    while let right = current.right {
        current = right
    }
    return current.val
}

let root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.right?.right = TreeNode(20)

if let maxValue = findMax(root) {
    print("Max value: \(maxValue)")
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findMax(root: TreeNode | null): number | null {
    if (!root) return null;
    let current: TreeNode = root;
    while (current.right !== null) {
        current = current.right;
    }
    return current.val;
}

const root = new TreeNode(10, new TreeNode(5), new TreeNode(15, null, new TreeNode(20)));
console.log("Max value:", findMax(root));