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?

Brutality

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).) – Demodulate

Answer 1

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.

Intermission

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. – Carrel

@Carrel You are welcome to suggest an edit, and I'll quickly approve it. – Intermission

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 is open coding findRightmostNode(). – Demodulate

@Demodulate 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. – Carrel

(@Carrel The fourth revision cries for return rightmost.left != null ? findRightmostNode(rightmost.left) : rightmost.parent.) – Demodulate

@Demodulate 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. – Carrel

Answer 2

No, that's wrong. Consider this BST:

        137
       /
      42
       \
        99

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!

Monocle

Thanks. I thought that BST is always balanced but it was not correct. – Brutality

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. – Guarantee

@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. – Monocle

Answer 3

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

Cooperage

Answer 4

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;

        }

Alpert

Answer 5

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

Wivina

Answer 6

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

Ouzel

It won't work for a BST that has elements inserted in this order: 5, 4, 3. – Bellebelleek

Answer 7

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

Alkalinity

Answer 8

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

Padgett

Answer 9

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.

Lietman

Answer 10

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

Croissant

Answer 11

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

Meyers

Answer 12

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.

Pentastich

Answer 13

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).

Bellebelleek

Answer 14

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

Dede

I guess 2ndMax() always returns null. (And look at the funny "syntax" decoration.) – Demodulate

Well, but it still returns the wrong node - try (a, ., (z, (b, ., (y,.,.), .)) (key, left child, right child; . for no child). – Demodulate

Answer 15

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

Footrest