How to find Second largest element in BST ?

• In an N-ary tree, the second largest value in the given tree to find and return the node. Return NULL if no node with required value is present.

• For example, in the given tree

Second largest node is 20.

• A simple solution is to traverse the array twice. In the first traversal the maximum value node to be find.
• In the second traversal find the greatest element node less than the element obtained in first traversal.
• This solution O(n) is the time complexity.
• To find the second largest element in a single traversal to be efficient solution.

Algorithm

[pastacode lang=”markdown” manual=”Initialize%20two%20nodes%20first%20and%20second%20to%20NULL%20as%2C%0Afirst%20%3D%20second%20%3D%20NULL%0A%0AStart%20traversing%20the%20tree%2C%0AIf%20the%20current%20node%20data%20say%20root-%3Ekey%20is%20greater%0Athan%20first-%3Ekey%20then%20update%20first%20and%20second%20as%2C%0Asecond%20%3D%20first%0Afirst%20%3D%20root%0AIf%20the%20current%20node%20data%20is%20in%20between%20first%20and%0Asecond%2C%20then%20update%20second%20to%20store%20the%20value%0Aof%20current%20node%20as%0Asecond%20%3D%20root%0A%0AReturn%20the%20node%20stored%20in%20second.” message=”” highlight=”” provider=”manual”/]

Sample Code in Java

[pastacode lang=”javascript” manual=”%2F%2F%20Java%20code%20to%20find%20second%20largest%20element%20in%20BST%20%0A%20%20%0A%2F%2F%20A%20binary%20tree%20node%20%0Aclass%20Node%20%7B%20%0A%20%20%0A%20%20%20%20int%20data%3B%20%0A%20%20%20%20Node%20left%2C%20right%3B%20%0A%20%20%0A%20%20%20%20Node(int%20d)%20%0A%20%20%20%20%7B%20%0A%20%20%20%20%20%20%20%20data%20%3D%20d%3B%20%0A%20%20%20%20%20%20%20%20left%20%3D%20right%20%3D%20null%3B%20%0A%20%20%20%20%7D%20%0A%7D%20%0A%20%20%0Aclass%20BinarySearchTree%20%7B%20%0A%20%20%0A%20%20%20%20%2F%2F%20Root%20of%20BST%20%0A%20%20%20%20Node%20root%3B%20%0A%20%20%0A%20%20%20%20%2F%2F%20Constructor%20%0A%20%20%20%20BinarySearchTree()%20%0A%20%20%20%20%7B%20%0A%20%20%20%20%20%20%20%20root%20%3D%20null%3B%20%0A%20%20%20%20%7D%20%0A%20%20%0A%20%20%20%20%2F%2F%20function%20to%20insert%20new%20nodes%20%0A%20%20%20%20public%20void%20insert(int%20data)%20%0A%20%20%20%20%7B%20%0A%20%20%20%20%20%20%20%20this.root%20%3D%20this.insertRec(this.root%2C%20data)%3B%20%0A%20%20%20%20%7D%20%0A%20%20%20%20%20%20%0A%20%20%20%20%2F*%20A%20utility%20function%20to%20insert%20a%20new%20node%20with%20given%20%20%0A%20%20%20%20key%20in%20BST%20*%2F%0A%20%20%20%20Node%20insertRec(Node%20node%2C%20int%20data)%20%0A%20%20%20%20%7B%20%0A%20%20%20%20%20%20%20%20%2F*%20If%20the%20tree%20is%20empty%2C%20return%20a%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20(node%20%3D%3D%20null)%20%7B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20this.root%20%3D%20new%20Node(data)%3B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20this.root%3B%20%0A%20%20%20%20%20%20%20%20%7D%20%0A%20%20%0A%20%20%20%20%20%20%20%20%2F*%20Otherwise%2C%20recur%20down%20the%20tree%20*%2F%0A%20%20%20%20%20%20%20%20if%20(data%20%3C%20node.data)%20%7B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20node.left%20%3D%20this.insertRec(node.left%2C%20data)%3B%20%0A%20%20%20%20%20%20%20%20%7D%20else%20%7B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20node.right%20%3D%20this.insertRec(node.right%2C%20data)%3B%20%0A%20%20%20%20%20%20%20%20%7D%20%0A%20%20%20%20%20%20%20%20return%20node%3B%20%0A%20%20%20%20%7D%20%0A%20%20%0A%20%20%20%20%2F%2F%20class%20that%20stores%20the%20value%20of%20count%20%0A%20%20%20%20public%20class%20count%20%7B%20%0A%20%20%20%20%20%20%20%20int%20c%20%3D%200%3B%20%0A%20%20%20%20%7D%20%0A%20%20%0A%20%20%20%20%2F%2F%20Function%20to%20find%202nd%20largest%20element%20%0A%20%20%20%20void%20secondLargestUtil(Node%20node%2C%20count%20C)%20%0A%20%20%20%20%7B%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Base%20cases%2C%20the%20second%20condition%20is%20important%20to%20%0A%20%20%20%20%20%20%20%20%2F%2F%20avoid%20unnecessary%20recursive%20calls%20%0A%20%20%20%20%20%20%20%20if%20(node%20%3D%3D%20null%20%7C%7C%20C.c%20%3E%3D%202)%20%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Follow%20reverse%20inorder%20traversal%20so%20that%20the%20%0A%20%20%20%20%20%20%20%20%2F%2F%20largest%20element%20is%20visited%20first%20%0A%20%20%20%20%20%20%20%20this.secondLargestUtil(node.right%2C%20C)%3B%20%20%0A%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%2F%2F%20Increment%20count%20of%20visited%20nodes%20%0A%20%20%20%20%20%20%20%20C.c%2B%2B%3B%20%0A%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20c%20becomes%20k%20now%2C%20then%20this%20is%20the%202nd%20largest%20%0A%20%20%20%20%20%20%20%20if%20(C.c%20%3D%3D%202)%20%7B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(%222nd%20largest%20element%20is%20%22%2B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20node.data)%3B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%20%0A%20%20%20%20%20%20%20%20%7D%20%0A%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%2F%2F%20Recur%20for%20left%20subtree%20%0A%20%20%20%20%20%20%20%20this.secondLargestUtil(node.left%2C%20C)%3B%20%20%0A%20%20%20%20%7D%20%0A%20%20%0A%20%20%20%20%2F%2F%20Function%20to%20find%202nd%20largest%20element%20%0A%20%20%20%20void%20secondLargest(Node%20node)%20%0A%20%20%20%20%7B%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20object%20of%20class%20count%20%0A%20%20%20%20%20%20%20%20count%20C%20%3D%20new%20count()%3B%20%20%0A%20%20%20%20%20%20%20%20this.secondLargestUtil(this.root%2C%20C)%3B%20%0A%20%20%20%20%7D%20%0A%20%20%0A%20%20%20%20%2F%2F%20Driver%20function%20%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%0A%20%20%20%20%7B%20%0A%20%20%20%20%20%20%20%20BinarySearchTree%20tree%20%3D%20new%20BinarySearchTree()%3B%20%0A%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20create%20following%20BST%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%2050%20%0A%20%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%20%20%5C%20%0A%20%20%20%20%20%20%20%20%20%2030%20%20%20%20%20%2070%20%0A%20%20%20%20%20%20%20%20%20%2F%20%20%5C%20%20%20%20%2F%20%20%5C%20%0A%20%20%20%20%20%20%2020%20%20%2040%20%2060%20%20%2080%20*%2F%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20tree.insert(50)%3B%20%0A%20%20%20%20%20%20%20%20tree.insert(30)%3B%20%0A%20%20%20%20%20%20%20%20tree.insert(20)%3B%20%0A%20%20%20%20%20%20%20%20tree.insert(40)%3B%20%0A%20%20%20%20%20%20%20%20tree.insert(70)%3B%20%0A%20%20%20%20%20%20%20%20tree.insert(60)%3B%20%0A%20%20%20%20%20%20%20%20tree.insert(80)%3B%20%0A%20%20%0A%20%20%20%20%20%20%20%20tree.secondLargest(tree.root)%3B%20%0A%20%20%20%20%7D%20%0A%7D%20″ message=”” highlight=”” provider=”manual”/]