Second largest element in BST

http://quiz.geeksforgeeks.org/second-largest-element-in-binary-search-tree-bst/

The second largest element is second last element in inorder traversal and second element in reverse inorder traversal. We traverse given Binary Search Tree in reverse inorder and keep track of counts of nodes visited. Once the count becomes 2, we print the node.

// A function to find 2nd largest element in a given tree.

void secondLargestUtil(Node *root, int &c)

{

    // Base cases, the second condition is important to

    // avoid unnecessary recursive calls

    if (root == NULL || c >= 2)

        return;

 

    // Follow reverse inorder traversal so that the

    // largest element is visited first

    secondLargestUtil(root->right, c);

 

    // Increment count of visited nodes

    c++;

 

    // If c becomes k now, then this is the 2nd largest

    if (c == 2)

    {

        cout << "2nd largest element is "

             << root->key << endl;

        return;

    }

 

    // Recur for left subtree

    secondLargestUtil(root->left, c);

}

algorithm - Second max in BST - Stack Overflow
The max element is the rightmost leaf in the BST. The second max is either its parent or its left child. So the solution is to traverse the BST to find the rightmost leaf and check its parent and left child.

public static int findSecondLargestValueInBST(Node root)
    {
        int secondMax;
        Node pre = root;
        Node cur = root;
        while (cur.Right != null)
        {
            pre = cur;
            cur = cur.Right;
        }
        if (cur.Left != null)
        {
            cur = cur.Left;
            while (cur.Right != null)
                cur = cur.Right;
            secondMax = cur.Value;
        }
        else
        {
            if (cur == root && pre == root)
                //Only one node in BST
                secondMax = int.MinValue;
            else
                secondMax = pre.Value;
        }
        return secondMax;
    }

http://blog.gainlo.co/index.php/2016/06/03/second-largest-element-of-a-binary-search-tree/
Read full article from algorithm - Second max in BST - Stack Overflow