Skip to main content

Sum of alternate leaf nodes in bst in ruby

Sum of alternate leaf nodes

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

#  Ruby program for
#  Sum of alternate leaf nodes in bst
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(data) 
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinarySearchTree 
	# Define the accessor and reader of class BinarySearchTree
	attr_reader :root, :alternate
	attr_accessor :root, :alternate
	def initialize() 
		self.root = nil
		self.alternate = false
	end

	#  Insert a new node element
	def addNode(data) 
		#  Create a new node
		node = TreeNode.new(data)
		if (self.root == nil) 
			#  When add first node in bst
			self.root = node
		else
 
			find = self.root
			#  Add new node to proper position
			while (find != nil) 
				if (find.data >= data) 
					if (find.left == nil) 
						#  When left child empty
						#  So add new node here
						find.left = node
						return
					else
 
						#  Otherwise
						#  Visit to left sub-tree
						find = find.left
					end

				else
 
					if (find.right == nil) 
						#  When right child empty
						#  So add new node here.
						find.right = node
						return
					else
 
						#  Visit to right sub-tree
						find = find.right
					end
				end
			end
		end
	end

	def leafSum(node) 
		if (node != nil) 
			if (node.left == nil && node.right == nil) 
				#  Case A
				#  When node is leaf node.
				#  Change status.
				self.alternate = !self.alternate
				#  Check node is alternate or not.
				if (self.alternate) 
					#  When get alternate node.
					return node.data
				end

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

		end

		return 0
	end

	def alternateLeafSum() 
		#  Reset alternate leaf node status
		self.alternate = false
		return self.leafSum(self.root)
	end

end

def main() 
	tree = BinarySearchTree.new()
	# 	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(), "\n")
end

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