Finding second largest element in a BST

Looking nice, BST!

It’s all fun and play till you have to get back to your roots. Your binary search tree roots I mean. The catch with this one was having to return not the largest but the second largest element in a binary search tree. Here’s the problem statement:

Write a method to find the 2nd largest element in a binary search tree given a sample binary tree node class:

#include <iostream>
#include <memory>
#include "lest.hpp"
using namespace std;
class BinaryTreeNode
{
public:
    int value_;
    BinaryTreeNode* left_;
    BinaryTreeNode* right_;
BinaryTreeNode(int value) :
        value_(value),
        left_(nullptr),
        right_(nullptr)
    {
    }
~BinaryTreeNode()
    {
        delete left_;
        delete right_;
    }
BinaryTreeNode* insertLeft(int value)
    {
        this->left_ = new BinaryTreeNode(value);
        return this->left_;
    }
BinaryTreeNode* insertRight(int value)
    {
        this->right_ = new BinaryTreeNode(value);
        return this->right_;
    }
};

Now that you’ve seen the question let’s see what we can do.

Let’s refresh the basics.

• What do we know about a BST? The right child will store a key value higher than that of the parent and the left child will store one lower. Clearly, we need to be going through the right path (pun intended).
• In-order traversal allows you to go through the binary tree in ascending order of key values.

Thus, we know the right-most element would be the largest and that is fairly easy to find. But we need the second largest.

We also know the second largest, would obviously be the left child of the largest, thanks to point #1.

But wait, what if the left child of the largest also had a right child. Which means the right child would be greater than the left child of the largest but lesser than the greatest in the tree. So our left child wouldn’t be the second largest.

Okay, now bear with me. That’s not the only issue.

What if the largest had no children?

So we clearly have two questions to answer. Both of which shouldn’t take long for you to figure out.

• To answer the second question: if the largest did not have a child, the second largest would obviously be the parent.
• Now the first problem, have we already answered it? Think about it. To find the second largest, we repeat this entire process to the sub-tree with the left child of the largest as the root.

Now that we’re on the same page about what we want to do, all we have to do now is go through an in-order traversal, get the right-most element which will be our largest element.

// find the largest item in the binary search tree
    const BinaryTreeNode* current = rootNode;
    const BinaryTreeNode* parent;
    while(current->right_ != NULL) {
        parent = current;
        current = current->right_;
    }
    const BinaryTreeNode* largest = current;
    const BinaryTreeNode* second_largest;

Next, if our largest element has no left sub-tree, the answer is simple: the second largest element would be the parent of our largest!

if(largest->left_ == NULL) {
        second_largest = parent;
        return second_largest->value_;
    }

Now if it does have a left sub-tree, we follow our initial procedure of finding the largest except with the left child of the largest as the root.

current = current->left_;
    while(current->right_ != NULL) {
        parent = current;
        current = current->right_;
    }
    second_largest = current;
    return second_largest->value_;

And here’s the final product!

int findSecondLargest(const BinaryTreeNode* rootNode)
{
    if (rootNode == NULL || (rootNode->left_ == NULL && rootNode->right_== NULL)) {
        throw invalid_argument("Tree must have at least 2 nodes");
    }
// find the largest item in the binary search tree
    const BinaryTreeNode* current = rootNode;
    const BinaryTreeNode* parent;
    while(current->right_ != NULL) {
        parent = current;
        current = current->right_;
    }
    const BinaryTreeNode* largest = current;
    const BinaryTreeNode* second_largest;
    if(largest->left_ == NULL) {
        second_largest = parent;
        return second_largest->value_;
    }
    current = current->left_;
    while(current->right_ != NULL) {
        parent = current;
        current = current->right_;
    }
    second_largest = current;
    return second_largest->value_;
}

Hope it helped!