Second largest element in binary search tree

Problem

Given a BST (Binary search tree), find the second largest element of it.

Examples

Example 1:

      1         
    /   \   
   0     2      

Input: root = [1,0,2]
Output: 1

Example 1:

	 1         
   /   \   
  0     2   
         \ 
          3

Input: root = [1,0,2,null, null, null, 3]
Output: 2

Solution

We have seen a similar problem - Kth largest element in Binary Search Tree.

Method 1 - Find the maximum twice

If you are quite familiar with all of these, you should be able to come up with this very straightforward solution: First, find the largest element of the BST and delete it. Then, find the largest element of the current BST, which is the 2nd largest element of the original BST.

But this does modification to the tree, and also time complexity is not O(h), where h is the height of the bst.

Method 2 - Inorder traversal and using array

Another approach can be we do the inorder traversal of the tree, and generate the array. Then, we return the second last element as the answer. But this is again bad, as time and space complexity is both O(n), where n is the number of nodes in the BST.

For eg. inorder traversal is [0, 1, 2, 3] in example 2, and 2nd last element is 2.

Method 3 - Reverse Inorder Traversal

We need to do reverse inorder traversal, as we need second largest element, but inorder traversal goes from small to large elements. We need it in reverse order.

We can use a counter variable. Count is 1 for largest element, and we will increase it, as the element we find is less than largest element. When our count == 2, we return the answer.

Code

Java

 class Solution {

	private int count = 0;

	private int secondLargest = 0;

	public int findSecondLargest(TreeNode root) {
		helper(root);
		return secondLargest;
	}

	// Helper method to perform reverse in-order traversal
	private void helper(TreeNode root) {
		if (root == null || count >= 2) {
			return; // Base case
		}

		// Traverse right subtree first (higher values)
		helper(root.right);

		// Increment the count and check if this is the second element
		if (++count == 2) {
			secondLargest = root.val;
			return;
		}

		// Traverse left subtree (lower values)
		helper(root.left);
	}
}

Complexity

• ⏰ Time complexity: O(h)
• 🧺 Space complexity: O(1)

Method 4 - Finding the second largest element using largest element

We can use following relation:

Traverse through the tree looking for the largest element.

• if the largest element has a left child, return the largest element of the left subtree.
• else, return the parent of the largest element.

Code

Java

public TreeNode getSecondLargest(TreeNode root) { 
    
    // we are looking at the right-most element 
    // (aka largest) and it has a left child
    // so we want the largest element in its left child
    if (root.right == null && root.left != null) {  
        return getLargest(root.left);  
    }  
    
    // we are looking at the parent of the largest element
    // and the largest element has no children
    // so this is the node we want
    if (root.right != null &&  
            root.right.left == null &&  
            root.right.right == null) {  
        return root;  
    }  
  
    // recurse on the right child until we match
    // one of the above cases
    return getSecondLargest(root.right);  
}