## Problem

You are given the root to a binary search tree. Find the *second* largest node in the tree and return it.
For example for the given binary search tree, return 3.

## Solution

It may be noted that in the following solutions, `NULL`

is returned if there are less than 2 nodes in the BST.

### Recursive Solution

Inorder traversal traverses the BST in a sorted way. Thus, if we perform a reverse inorder traversal, we will get the largest node first and then second largest node and so on.

In the following solution `k`

is set to 2, since we want to find the second
largest node. In the reverse inorder traversal function, `k`

is decremented
every time we are at the current node (revere inorder traversal is performed
by visiting right node first, then current node and then the left node). As soon
as `k`

is `0`

, the value of the current node is returned.

```
int secondLargestElement = NULL;
void reverseInorder(TreeNode* root, int &k) {
if (root == nullptr) return;
reverseInorder(root -> right, k);
--k;
if (k == 0) {
secondLargestElement = root -> val;
return;
}
reverseInorder(root -> left, k);
}
int secondLargestRecursive(TreeNode* root) {
int k = 2;
reverseInorder(root, k);
return secondLargestElement;
}
```

**Time Complexity**: $O(h)$, where $h$ is the height of the BST which can go as maximum as the number of nodes for a skewed BST.**Space Complexity**: $O(h)$ (where $h$ is the height of the BST) for the implicit stack required for recursion.

### Iterative solution

For iterative solution we have to consider few cases:

**Right subtree is empty:**The answer will be inorder predecessor to the root.**Right-most node is not a leaf node**: The answer will be the left child of the right most node.**Right-most node is a leaf node**: The answer will be the parent to the right-most node.

```
int secondLargestIterative(TreeNode* root) {
TreeNode* prevNode;
// empty BST
if (!root) return NULL;
// less than 2 nodes in the BST
if (!root -> right and !root -> left) return NULL;
// right subtree is empty
if (!root -> right) {
root = root -> left;
while(root -> right) {
root = root -> right;
}
return root -> val;
}
// traverse to the right most node
while(root -> right) {
prevNode = root;
root = root -> right;
}
// empty right most node
if (!root -> right and !root -> left) {
return prevNode -> val;
}
return root -> left -> val;
}
```

**Time Complexity**: $O(h)$, where $h$ is the height of the BST which can go as
maximum as the number of nodes for a skewed BST.

**Space Complexity**: $O(1)$.