Skip to main content

Check for foldable binary tree in ruby

Ruby program for Check for foldable binary tree. Here problem description and explanation.

#  Ruby program for
#  Check if binary tree is foldable binary tree
#  Using recursion

#  Binary Tree Node
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(data) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end
end

class BinaryTree 
	# Define the accessor and reader of class BinaryTree
	attr_reader :root
	attr_accessor :root
	def initialize() 
		self.root = nil
	end
	def isFoldable(leftRoot, rightRoot) 
		if (leftRoot == nil && rightRoot == nil) 
			#  When both node empty
			return true
		elsif(leftRoot != nil && rightRoot != nil &&
              self.isFoldable(leftRoot.left, rightRoot.right) && 
              self.isFoldable(leftRoot.right, rightRoot.left)) 
			#  When
			#  Valid the properties of foldable tree
			return true
		end
		#  Fail case
		return false
	end

	#  Display tree element inorder form
	def inorder(node) 
		if (node != nil) 
			#  Visit to left subtree
			self.inorder(node.left)
			#  Print node value
			print("  ", node.data)
			#  Visit to right subtree
			self.inorder(node.right)
		end
	end
end

def main() 
	#  Create new tree
	tree = BinaryTree.new()
	#   Binary Tree
	#  -----------------------
	#       5
	#     /   \
	#    7     4
	#   /       \
	#  1         2
	#   \       /
	#    2     5
	#  Binary tree nodes
	tree.root = TreeNode.new(5)
	tree.root.left = TreeNode.new(7)
	tree.root.right = TreeNode.new(4)
	tree.root.left.left = TreeNode.new(1)
	tree.root.right.right = TreeNode.new(2)
	tree.root.right.right.left = TreeNode.new(5)
	tree.root.left.left.right = TreeNode.new(2)
	#  Display Tree elements
	tree.inorder(tree.root)
	result = tree.isFoldable(tree.root.left, 
                             tree.root.right)
	if (result == true) 
		print("\n Foldable Tree\n")
	else
		print("\n Not Foldable Tree\n")
	end

	#         5
	#       /   \
	#      7     4
	#     /       \
	#    1         2
	#     \       /
	#      2     5
	#       \
	#        3  
	#  Case 2
	tree.root.left.left.right.right = TreeNode.new(3)
	tree.inorder(tree.root)
	result = tree.isFoldable(tree.root.left, 
                             tree.root.right)
	if (result == true) 
		print("\n Foldable Tree\n")
	else
		print("\n Not Foldable Tree\n")
	end

end

main()

Output

  1  2  7  5  4  5  2
 Foldable Tree
  1  2  3  7  5  4  5  2
 Not Foldable Tree




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