Skip to main content

Second largest element in BST in python

Second largest element in BST

Python program for Second largest element in BST. Here mentioned other language solution.

#  Python 3 program for
#  Second largest element in BST
class TreeNode :
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None

class BinarySearchTree :
	def __init__(self) :
		self.root = None
		self.result = None
		self.counter = 0
	
	#  Insert a node element
	def addNode(self, data) :
		#  Create a new node
		node = TreeNode(data)
		if (self.root == None) :
			#  When adds a first node in bst
			self.root = node
		else :
			find = self.root
			#  Add new node to proper position
			while (find != None) :
				if (find.data >= data) :
					if (find.left == None) :
						#  When left child empty
						#  So add new node here
						find.left = node
						return
					else :
						#  Otherwise
						#  Visit left sub-tree
						find = find.left
					
				else :
					if (find.right == None) :
						#  When right child empty
						#  So add new node here
						find.right = node
						return
					else :
						#  Visit right sub-tree
						find = find.right

	#  Find second largest element in a binary search tree
	def findSecondBig(self, node) :
		if (node != None) :
			#  Visit to right subtree
			self.findSecondBig(node.right)
			if (self.counter == 2) :
				return
			
			if (self.result == None or 
                self.result.data > node.data) :
				#  Modified counter variable by one
				self.counter += 1
				self.result = node
			
			#  Visit to left subtree
			self.findSecondBig(node.left)
		
	
	def secondLargest(self) :
		if (self.root == None) :
			#  When BST are empty
			print("Empty Binary Search Tree")
		else :
			#  Reset value
			self.counter = 0
			self.result = None
			#  Find second largest
			self.findSecondBig(self.root)
			if (self.result == None or self.counter < 2) :
				#  If In case 2nd Largest node are
				#  Not exist in binary search tree
				print("Second Largest node are not exist")
			else :
				print("Second largest node : ", self.result.data)

def main() :
	tree = BinarySearchTree()
	#  Binary Search Tree
	#  -------------------
	#        7
	#       / \
	#      /   \
	#     4     10
	#    / \   / \
	#   3   5 8   10
	#          \    \
	#           9   10
	#  Add node
	tree.addNode(7)
	tree.addNode(4)
	tree.addNode(3)
	tree.addNode(5)
	tree.addNode(10)
	tree.addNode(8)
	tree.addNode(10)
	tree.addNode(9)
	tree.addNode(10)
	tree.secondLargest()

if __name__ == "__main__": main()

Output

Second largest node :  9




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment