LinkedIn Interview Question: Find the second largest eleme... | Glassdoor

Interview Question

Data Scientist Intern Interview Mountain View, CA

Find the second largest element in a Binary Search Tree

java, data structures, algorithm

Interview Answer

16 Answers


find the right most element. If this is a right node with no children, return its parent. if this is not, return the largest element of its left child.

Interview Candidate on Feb 25, 2012

One addition is the situation where the tree has no right branch (root is largest). In this special case, it does not have a parent.
So it's better to keep track of parent and current pointers, if different, the original method by the candidate works well, if the same (which means the root situation), find the largest of its left branch.

Anonymous on Mar 6, 2012

if (root == null || (!root.hasRightChild() ) { return null;}
else return findSecondGreatest(root, root.getValue());

value findSecondGreatest(Node curr, value oldValue) {
      if(curr.hasRightChild()) {
            return (findSecondGreatest( curr.getRightChild(), curr.value));
       else return oldValue;

Anon on Apr 12, 2012

The above answer is also wrong;

Node findSceondLargest(Node root) {
  // If tree is null or is single node only, return null (no second largest)
  if (root==null || (root.left==null && root.right==null)) return null;
  Node parent = null, child = root;
  // find the right most child
  while (child.right!=null) {
      parent = child;
      child = child.right;
   // if the right most child has no left child, then it's parent is second largest
   if (child.left==null) return parent;
   // otherwise, return left child's rightmost child as second largest
   child = child.left;
   while (child.right!=null) child = child.right;
   return child;

mindpower on Jun 2, 2012

Soln by "mindpower" works. Thank you.
I am trying to solve a similar problem
Find the 2nd nearest high(in in-order traversal) value for a given node
Eg: Given nums: 12 7 14 3, construct a BST.
If the given value is: 7 then we should return 14 (in the sort order: 3, 7, 12, 14)
if the given value is: 3 then we should return 12 (in the sort order: 3, 7, 12, 14)

vesadi on Jul 3, 2012

Generic solution in C# for any k. Notice that this example can be easily changed to find the k-th smallest node by doing a depth-first recursion on root.Left first, and then a tail recursion on root.Right.

public Node GetKthLargest(int k)
{ return GetKthLargest(ref k, this.Root); }

Node GetKthLargest(ref int k, Node root)
    if (root == null || k < 1)
        return null;

    var node = GetKthLargest(ref k, root.Right);
    if (node != null)
        return node;

    if (--k == 0)
        return root;
    return GetKthLargest(ref k, root.Left);

Erhhung on Aug 14, 2012

recursion is not needed.

SecondLargest(Node root, Node secondLarge)

        return root.left;

    Node secondLargest = root;

    return secondLargest;

Techie on Oct 6, 2012

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

Anonymous on Oct 11, 2013

In-order traverse the tree. The second last element in the array in the answer.

test on Oct 3, 2014

In Python:

def find_second_largest_bst_element(root, parent=None):
    if parent is None: # BST root
        if root.right is None: # no right subtree
            if root.left is not None: # if a left subtree exists...
                return root.left
            else: # root is the only element of the BST
                return False
        if root.right is None: # right-most element
            if root.left is not None: # left subtree exists
                return root.left
            else: # leaf
                return parent
        else: # check right subtree
            find_second_largest_bst_element(root.right, root)


d_t on Oct 23, 2014

For kth smallest, descend the left subtree first.

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def findKthLargest(root, k):
    global count
    if root is None:
    findKthLargest(root.right, k)
    count += 1
    if count == k:
        print root.value
    findKthLargest(root.left, k)

count = 0
r = Node(10, Node(5, Node(2), Node(7)), Node(30, Node(22), Node(32)))
findKthLargest(r, 3)

General case for kth largest in python on Nov 24, 2014

// solution in java
// main routine
Node findSecondMax(Node root)
    if(root == null || (root.left == null && root.right == null)
        return null;

        Node max = findMax(root);
        return (max.parent == null) ? findMax(max.left) : max.parent;

//helper routine, recursive implementation.... can also be done non-recursively
Node findMax(Node root)
    return (root.right == null) ? root : findMax(root.right);

ytn01 on Jun 23, 2015

Find the largest number in the binary tree and delete it. And again find the largest number.
Short and fast.

Anonymous on Feb 9, 2017

Reverse in-order traversal of the BST, keeping a count of # of visited nodes. This methods works great to return the kth largest element in a BST.

Anonymous on Apr 3, 2017

mindpower's solution looks right

Anonymous on Apr 26, 2017

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Add Answers or Comments

To comment on this, Sign In or Sign Up.