Find Second Largest Node In BST

, , , ,

Question

Given the root to a binary search tree, find the second largest node in the tree.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: Root of below BST
    10
   /
  5

Output:  5


Input: Root of below BST
        10
      /   \
    5      20
             \ 
              30 

Output:  20

Solution

Brute force solution is more obvious, which means we just need traversal the whole tree and get the node we want, it costs O(n). But we want to improve it due to the property of BST. Actually, if we want to get the sorted result, we have to use inorder during the process, but normally, we use [left subtree], [visit], right subtree], that gives us ascending order. But for our problem we want to get the second largest node, so, we just need to change the order I mentioned before,[right subtree], [visit], left subtree]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// time:O(Height of Tree ~ logN)
    public int res = 0, count = 0;
    public int secondLargest(TreeNode root) {
        if (root == null) return -1;
        dfs(root);
        return res;
    }

    public void dfs(TreeNode root) {
        if (root == null || count > 2) return;
        dfs(root.right);
        count++;
        if (count == 2) {
            res = root.val;
        }
        dfs(root.left);
    }

Reference