How to find maximum value in a Binary Search Tree (BST)

The naive approach, visit all nodes, and compare a value in each node. A better approach is to use the definition of a binary search tree.

A Binary Search Tree (BST) is a binary tree where each node has a key and meet the following requirements:

• The left subtree of a node contains nodes with keys smaller then the node's key
• The right subtree of a node contains nodes with keys larger then the node's key
• The left and right subtrees are binary search trees

In other words, the rightmost node in a BST has a maximum value.

Examples

Let's see a couple of BST examples. As we see the rightmost node has a maximum value and the rightmost node it's a right node without a right child.

 

 

 

In this example, the right node has the maximum value.

Algorithm

The answer to the question "How to find maximum value in a Binary Search Tree (BST)":

• always go to the right until finding a node without a right child. This node will have maximum value in a BST.

The last question we need to answer before start writing code. What should the algorithm do if a BST is empty? For simplicity, let's return -1 if a BST is empty.

Note: ask a question on your interview. Is it ok to return a -1 if BST is empty? BST can store not only positive but negative values as well.

    public int MaxValue(TreeNode root)
    {
        if (root == null)
        {
            return -1;
        }

        TreeNode node = root;
        while (node.Right != null)
        {
            node = node.Right;
        }

        return node.Value;
    }