Skip to main content

Sum of alternate leaf nodes in bst in python

Sum of alternate leaf nodes

Python program for Sum of alternate leaf nodes in bst. Here more solutions.

#  Python 3 program for
#  Sum of alternate leaf nodes 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.alternate = False
	
	#  Insert a new node element
	def addNode(self, data) :
		#  Create a new node
		node = TreeNode(data)
		if (self.root == None) :
			#  When add 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 to 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 to right sub-tree
						find = find.right
	
	def leafSum(self, node) :
		if (node != None) :
			if (node.left == None and 
                node.right == None) :
				#  Case A
				#  When node is leaf node.
				#  Change status.
				self.alternate = not self.alternate
				#  Check node is alternate or not.
				if (self.alternate) :
					#  When get alternate node.
					return node.data
				
			else :
				#  Case B
				#  When node is internal
				#  Visit left and right subtree and
				#  Find alternate node.
				return self.leafSum(node.left) + \
				self.leafSum(node.right)
			
		
		return 0
	
	def alternateLeafSum(self) :
		#  Reset alternate leaf node status
		self.alternate = False
		return self.leafSum(self.root)
	

def main() :
	tree = BinarySearchTree()
	# 	Binary search tree
	#    -------------------
	#       5
	#      /  \  
	#     /    \ 
	#    /      \
	#   3        19
	#  / \     /   \
	# 2   4   8     31
	#       / \    / \
	#      7   15 25  50  
	#  Add tree node
	tree.addNode(5)
	tree.addNode(3)
	tree.addNode(19)
	tree.addNode(2)
	tree.addNode(4)
	tree.addNode(8)
	tree.addNode(31)
	tree.addNode(7)
	tree.addNode(25)
	tree.addNode(15)
	tree.addNode(50)
	#  Test
	print(tree.alternateLeafSum())

if __name__ == "__main__": main()

Output

34




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