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