Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/cabf4820725eb5a148bc1320b31ea39d to your computer and use it in GitHub Desktop.
Save jianminchen/cabf4820725eb5a148bc1320b31ea39d to your computer and use it in GitHub Desktop.
Find second largest element in the binary search tree
/*
10:32 pm
Find second largest element in binary search tree
stack iterative traversal of first 2 elements
time o(n) space o(n)
if tree has less than 2 elements return null
Ex 1 res=5
10* no right child, so no larger element, 10 is largest possible element
5* 5,10
10* no right child, so no larger element, 10 is largest possible element
5* 5,10 since 5 has right child, right child must be larger
1 8* 8,10 ret 8
10* no right child, so no larger element, 10 is largest possible element
5* 5,10 since 5 has right child, right child must be larger
1 8* 8,10 child is left which is smaller, does not affect result
6
10* no right child, so no larger element, 10 is largest possible element
5* 5,10 since 5 has right child, right child must be larger
1 8* 8 has right child, has to be larger
6 9 9,10
result=9
10//10
9//9,10
8//left is smaller, queue is full, so doesn't matter
7
ascending pq
3
2
1
4
2
1 3
[4, 2, 3]
10
5 15*
8 13*
14*
3*
2*
1*
*/
10X,13X,14,15
public int secondLargestBSTNode(TreeNode root){
//null check, return -1
int result = -1;
PriorityQueue<Integer>pq=new PriorityQueue<>();
while(root != null){//2
pq.offer(root.val);//1,2,3
if(pq.size()>2){
pq.poll();//2,3
}
if(root.right != null){
root = root.right;//
}
else{
root = root.left;//null
}
}
//need check pq.size()==2
return pq.poll();//14
}
time
tree ologn
k=2
o*k (log n)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment