Second largest element in BST in python

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
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