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

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

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❯

Solution Explanation

Case 1: A Normal Binary Search Tree

In a typical BST, all nodes in the right subtree are greater than the current node, and all nodes in the left subtree are smaller. Therefore, to find the maximum value, we can keep moving to the right child of each node until we reach a node that has no right child. That node holds the maximum value.

For example, in the tree [4, 2, 6, 1, 3, 5, 7], the path to the maximum is: 4 → 6 → 7. Since 7 has no right child, it is the maximum.

Case 2: Tree Has Only One Node

If the BST has just one node, then that node is both the minimum and the maximum. There are no children to traverse, so the answer is immediate. For instance, in [10], the maximum is clearly 10.

Case 3: The Tree is Empty

If the tree is empty, there are no nodes to consider. In this case, the correct return value depends on the programming language you use — often it's null, None, or similar. It simply indicates the absence of any data in the tree.

Case 4: Right-Skewed Subtree

Sometimes, the right subtree contains additional levels of depth. We keep traversing right until the very last node. For example, in the tree [15, 10, 20, null, null, 18, 25], we move from 15 → 20 → 25. Since 25 has no right child, it is the maximum.

This property of BSTs makes it very efficient to find the maximum — there's no need to explore the entire tree, just the right edges.

Algorithm Steps❯

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

Code

Python
Java
JavaScript
C
C++
C#
Go
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

# Example usage:
if __name__ == '__main__':
    # Construct BST:
    #         10
    #        /  \
    #       5    15
    #             \
    #              20
    root = TreeNode(10, TreeNode(5), TreeNode(15, None, TreeNode(20)))
    print('Max value:', findMax(root))