Second max in BST

Question

This is an interview question. Find the second max in BST.

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.

Does it make sense?

`The max element is the rightmost leaf in the BST.` No, with a "regular" BST having a key in each node it is "the rightmost node", but not a leaf: think a tree containing just the root and a leaf as a left child (the rightmost without doubt). (There are "leaf search trees" where all valid values are at the leaves (think string keys and the nodes just carrying prefixes allowing to decide _left or right_).) — greybeard, Oct 18 '16 at 05:18

score 31 · Answer 1 · answered Jul 11 '12 at 04:16

31

No, that's wrong. Consider this BST:

Here, the second-to-max value is the rightmost child of the left child of the max value. Your algorithm will need to be updated so that you check the parent of the max value, or the rightmost subchild of the left child of the max.

Also, note that the max is not necessarily the rightmost leaf node, it's the node at the bottom of the right spine of the tree. Above, 137 is not a leaf.

Hope this helps!

answered Jul 11 '12 at 04:16

templatetypedef

362,284
104
897
1,065

Thanks. I thought that BST is always _balanced_ but it was not correct. – Michael Jul 11 '12 at 13:35
`99 (root) / 42 (left child of 99) \ 137 (right child of 42)` Isn't this a BST? In this case the max isn't the node at the bottom of the right spine of the tree. – Archit Verma Apr 08 '16 at 14:43
2

@ArchitVerma I don't think that's a valid BST because if 137 is a right child of 42 and 42 is a left child of 99, then 137 would have to be less than 99, which it isn't. – templatetypedef Apr 08 '16 at 18:32

score 15 · Accepted Answer · edited Dec 20 '16 at 19:36

15

Recall that you can list the nodes of a BST in reverse order by doing a modified inorder traversal where you explore the right subtree first. This leads to a simple algorithm:

Node rightmost = findRightmostNode(root)
if (rightmost.left != null) {
    return findRightmostNode(rightmost.left)
else{
    return rightmost.parent
}

It would return null if the tree has only one element.

edited Dec 20 '16 at 19:36

alvarosg

330
2
7

answered Jul 11 '12 at 04:24

Sergey Kalinichenko

714,442
84
1,110
1,523

No problem! ;) And you probably can make it nicer by calling `findRightmostNode(root)` outside the if statement. Essentially you need to find the right-most element of the left subtree, or the parent, of the right-most element. Essentially: 1. Find rightmost element from root. 2. If that element does not have a left subtree, return parent. If it has a left subtree, return right-most element of left subtree. – alvarosg Dec 20 '16 at 18:58
@alvarosg You are welcome to suggest an edit, and I'll quickly approve it. – Sergey Kalinichenko Dec 20 '16 at 19:01
Does the root being the rightmost node really deserve special handling? I don't think so (might require `findRightmostNode()` to accept (&return) `null`) - if you took that out, the remaining difference to [user2268025's 10 month younger, "uncommented" answer](http://stackoverflow.com/a/15936993/3789665) is open coding `findRightmostNode()`. – greybeard Dec 20 '16 at 19:17
@greybeard Yes, I guess there are only so many ways of going to the last node of a BST, and then go to the previous. I suggested the correction because this is at the top, and what most people will read. – alvarosg Dec 20 '16 at 19:22
(@alvarosg The fourth revision _cries_ for `return rightmost.left != null ? findRightmostNode(rightmost.left) : rightmost.parent`.) – greybeard Dec 20 '16 at 20:51
@greybeard I personally love the ternary operator as well :D but from the point for view of code legibility it is not always the best choice. Specially considering that the question does not ask for a particular implementation, leaving more pseudocodish-like may be better. – alvarosg Dec 21 '16 at 20:05

score 10 · Answer 3 · answered Apr 10 '13 at 21:43

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;
    }

score 7 · Answer 4 · answered Jul 19 '17 at 05:56

Much easier iterative approach with Time complexity O(logN) and Space complexity O(1)

public static void main(String[] args) {    
        BinaryTreeNode result=isBinarySearchTree.secondLargest(rootNode);

            System.out.println(result.data);
        }

        private BinaryTreeNode secondLargest(BinaryTreeNode node) {

            BinaryTreeNode prevNode=null; //2nd largest Element
            BinaryTreeNode currNode=node;
            if(null == currNode)
                return prevNode;

            while(currNode.right != null){
                prevNode=currNode;
                currNode=currNode.right;
            }
            if(currNode.left != null){
                currNode=currNode.left;
                while(currNode.right != null){
                    currNode=currNode.right;
                }
                prevNode=currNode;
            }

            return prevNode;

        }

score 5 · Answer 5 · answered Aug 31 '12 at 23:55

The algo can be as follows

1. find the largest number in the tree. 

  private static int findLargestValueInTree(Node root) {
    while (root.right != null) {
     root = root.right;
    }
    return root.data;
  }

2. Find the largest number in the tree that is smaller than the number we found in step 1

 public static int findSecondLargest(Node root, int largest, int current) {
   while (root != null) {
    if (root.data < largest) {
      current = root.data;
      root = root.right;
    } else {
      root = root.left;
   }
   }
  return current;
 }

'current' keeps track of the current largest number which is smaller than the number found in step1

score 2 · Answer 6 · answered Jan 02 '17 at 03:16

2

Simple javascript implementation.

function Node (value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right; 
}

function second (node, prev, wentLeft) {
    if (node.right) {
        return second(node.right, node, wentLeft);
    } else if (node.left) {
        return second(node.left, node, true);
    } else {
        if (wentLeft) return node.value;
        return prev.value;
    }
}
second(root);

answered Jan 02 '17 at 03:16

user3795309

136
1
9

It won't work for a BST that has elements inserted in this order: 5, 4, 3. – Shail Aug 12 '18 at 20:54

Sergey Korolev · Answer 7 · 2013-02-09T13:12:55.870

One traversal variant:

   public Tree GetSecondMax(Tree root)
    {
        Tree parentOfMax = null;

        var maxNode = GetMaxNode(root, ref parentOfMax);

        if (maxNode == root || maxnode.left != null)
        {
            // if maximum node is root or have left subtree, then return maximum from left subtree
            return GetMaxNode(maxnode.left, ref parentOfMax);
        }

        // if maximum node is not root, then return parent of maximum node
        return parentOfMax;
    }

    private Tree GetMaxNode(Tree root, ref Tree previousNode)
    {
        if (root == null || root.right == null)
        {
            // The most right element have reached
            return root;
        }

        // we was there
        previousNode = root;

        return GetMaxNode(root.right, ref previousNode);
    }

score 1 · Answer 8 · answered Oct 11 '13 at 21:32

int getmax(node *root)
{
    if(root->right == NULL)
    {
        return root->d;
    }
    return getmax(root->right);
}


int secondmax(node *root)
{
    if(root == NULL)
    {
        return -1;
    }

    if(root->right == NULL && root->left != NULL)
    {
        return getmax(root->left);
    }

    if(root->right != NULL)
    {
        if(root->right->right == NULL && root->right->left == NULL)
        {
            return root->d;
        }
    }

    return secondmax(root->right);
}

score 1 · Answer 9 · answered Sep 21 '14 at 05:09

A very intuitive way to think about this is considering the following two cases. Let second largest Node as S, and largest node as L.

i) S is inserted to the BST "earlier" than L. ii) S is inserted to the BST "later" than L.

For the first case, it is obvious that L is the right child of S. It is because any node except for L is smaller than S, therefore will not be put on the right side of S. Therefore when L is being put, it will be the right child of S.

For the second case, by the time when S is inserted, L will the be right most node in the BST. Obviously, L wouldn't have a right child because it is the largest. However, L could have its own left subtree. When S is inserted, S will follow to "right path" until it meets L and then turn left to go to the left subtree of L. Here, we know that all of the nodes in L's left subtree are smaller than S, so S will be the rightmost node in the subtree.

score 1 · Answer 10 · answered Jun 03 '16 at 09:02

int getSecondLargest(Node root){
    if(root==null)
        return 0;
    Node curr=root;
    Node prev=root;
    //Go to the largest node
    while(curr.right != null){
        prev = curr;
        curr= curr.right;
    }
    //If largest Node has left child, Then largest element of tree with its root as largest.left will be the second largest number.
    if(curr.left == null)
        return prev.data;
    else
        return findLargest(curr.left);
}

int findLargest(Node root){
    // No need toi check for null condition as in getSecondLargest method, its already done.
    Node curr=root;
    //To find largest just keep on going to right child till leaf is encountered.
    while(curr.right != null){
        curr = curr.right;
    }
    return curr.data;
}

score 1 · Answer 11 · answered Oct 17 '16 at 22:53

I would do it by going though the tree from biggest to smallest element and returning value when asked position is reached. I implemented similar task for second largest value.

void BTree::findSecondLargestValueUtil(Node* r, int &c, int &v)
{
    if(r->right) {
        this->findSecondLargestValueUtil(r->right, c, v);
    }

    c++;

    if(c==2) {
        v = r->value;
        return;
    }

    if(r->left) {
        this->findSecondLargestValueUtil(r->left, c, v);
    }
}


int BTree::findSecondLargestValue()
{
    int c = 0;
    int v = -1;

    this->findSecondLargestValueUtil(this->root, c, v);

    return v;
}

score 1 · Answer 12 · answered Jul 19 '17 at 06:06

You are close to the right answer.

Here is my attempt at an intuitive answer.

The greatest node is the right most node.

Whatever is under the right most node's left sub-tree is greater than all elements except the right most node. Therefore the greatest node in this sub-tree is the answer.

If there is no left sub-tree then the parent of the right most node is the one that is greater than all the other nodes except the right most node.

score 1 · Answer 13 · answered Aug 12 '18 at 21:08

The idea is to go all the way to the right until there is nothing on the right. If there's a left, take it and then go all the way to the right. If you took a left, the answer is the last node encountered. Otherwise the answer is the second-last node you encountered.

Here's a recursive solution in Java:

public TreeNode getSecondLargest(TreeNode root) {
    if(root == null || (root.left == null && root.right == null))
        throw new IllegalArgumentException("The tree must have at least two nodes");
    return helper(root, null, false);
}

private TreeNode helper(TreeNode root, TreeNode parent, boolean wentLeft) {
    if(root.right != null) return helper(root.right, root, wentLeft);
    if(root.left != null && !wentLeft) return helper(root.left, root, true);

    if(wentLeft) return root;
    else return parent;
}

The time complexity is O(lg n).

Anurag sinha · Answer 14 · 2020-10-20T13:37:09.483

1

This Algorithm to find 2nd Max Element in a BST , will take Time Complexity: O(n) --> in worst case where tree is a right skew tree. And if the Tree is balanced Tree then the Time Complexity is O(height) ie O(log n) And Same Goes with Space Complexity as well: O(n) --> in worst case O(log n) --> when Tree is balanced.

public TreeNode secondMax(TreeNode root){
    return helper(root,null);
}
private TreeNode helper(TreeNode root,TreeNode prev){
    if(root==null)
        return root;
    if(root.right==null && root.left!=null)
        return root.left;
    else if(root.right==null && root.left==null)
        return prev;
    return helper(root.right,root);
}

edited Oct 20 '20 at 13:37

answered Oct 19 '20 at 09:58

Anurag sinha

89
1
2

1

I guess `2ndMax()` always returns `null`. (And look at the funny "syntax" decoration.) – greybeard Oct 19 '20 at 12:44
Well, but it still returns the wrong node - try `(a, ., (z, (b, ., (y,.,.), .))` (*key*, *left child*, *right child*; `.` for *no child*). – greybeard Oct 20 '20 at 16:54

score 0 · Answer 15 · answered Feb 10 '17 at 20:03

This algorithm does one run on the tree and returns the largest item at Item1 and second largest at Item2. The sort calls are O(1) because they are independent of the tree size. So the total time complexity is O(N) and space complexity is O(log(N)) when the tree is balanced.

public static Tuple<int, int> SecondLargest(TreeNode<int> node)
{
    int thisValue = node.Value;
    if ((node.Left == null || node.Left.Right == null) && node.Right == null)
    {
        return new Tuple<int, int>(thisValue, -int.MaxValue);
    }
    else if (node.Left == null || node.Left.Right == null)
    {
        Tuple<int, int> right = SecondLargest(node.Right);
        List<int> sortLargest = new List<int>(new int[] { right.Item1, right.Item2, thisValue });
        sortLargest.Sort();
        return new Tuple<int, int>(sortLargest[2], sortLargest[1]);
    }
    else if (node.Right == null)
    {
        Tuple<int, int> left = SecondLargest(node.Left.Right);
        List<int> sortLargest = new List<int>(new int[] { left.Item1, left.Item2, thisValue });
        sortLargest.Sort();
        return new Tuple<int, int>(sortLargest[2], sortLargest[1]);
    }
    else
    {
        Tuple<int, int> left = SecondLargest(node.Left.Right);
        Tuple<int, int> right = SecondLargest(node.Right);
        List<int> sortLargest = new List<int>(new int[] { left.Item1, left.Item2, right.Item1, right.Item2, thisValue });
        sortLargest.Sort();
        return new Tuple<int, int>(sortLargest[4], sortLargest[3]);
    }
}

Second max in BST

15 Answers15

Linked