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

Interview Question

Data Scientist Intern Interview Mountain View, CA (US)

Find the second largest element in a Binary Search Tree

Tags:
java, data structures, algorithm
Answer

Interview Answer

16 Answers

23

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 25-Feb-2012
5

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 06-Mar-2012
1

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 12-Apr-2012

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

13

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 02-Jun-2012
0

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 03-Jul-2012
0

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 14-Aug-2012
2

recursion is not needed.

SecondLargest(Node root, Node secondLarge)
{

    if(root.right==null)
        return root.left;

    Node secondLargest = root;
    while(secondLargest.right.right==null)
        secondLargest=secondLargest.right;

    return secondLargest;
}

Techie on 06-Oct-2012
2

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 11-Oct-2013
3

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

test on 03-Oct-2014
0

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
    else:
        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)

find_second_largest_bst_element(root)

d_t on 23-Oct-2014
0

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:
        return
    findKthLargest(root.right, k)
    count += 1
    if count == k:
        print root.value
        return
    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 24-Nov-2014
0

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

    else
    {
        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 23-Jun-2015
0

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

Anonymous on 09-Feb-2017
0

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 03-Apr-2017
0

mindpower's solution looks right

Anonymous on 26-Apr-2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.