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

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

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 &lt; 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-&gt;right == NULL)
{
return root-&gt;d;
}
return getmax(root-&gt;right);
}

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

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

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

return secondmax(root-&gt;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 &amp;&amp; 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

One or more comments have been removed.