Skip to main content

Check for foldable binary tree in golang

Go program for Check for foldable binary tree. Here more information.

package main
import "fmt"
/* 
  Go program for
  Check if binary tree is foldable binary tree
  Using recursion
*/
// Binary Tree Node
type TreeNode struct {
	data int
	left * TreeNode
	right * TreeNode
}
func getTreeNode(data int) * TreeNode {
	// return new TreeNode
	return &TreeNode {
		data,
		nil,
		nil,
	}
}
type BinaryTree struct {
	root * TreeNode
}
func getBinaryTree() * BinaryTree {
	// return new BinaryTree
	return &BinaryTree {
		nil,
	}
}
func(this BinaryTree) isFoldable(leftRoot, 
					rightRoot *TreeNode) bool {
	if leftRoot == nil && rightRoot == nil {
		// When both node empty
		return true
	} else if leftRoot != nil && rightRoot != nil && 
		this.isFoldable(leftRoot.left, rightRoot.right) && 
		this.isFoldable(leftRoot.right, rightRoot.left) {
		// When
		// Valid the properties of foldable tree
		return true
	}
	// Fail case
	return false
}
// Display tree element inorder form
func(this BinaryTree) inorder(node * TreeNode) {
	if node != nil {
		// Visit to left subtree
		this.inorder(node.left)
		// Print node value
		fmt.Print("  ", node.data)
		// Visit to right subtree
		this.inorder(node.right)
	}
}
func main() {
	// Create new tree
	var tree * BinaryTree = getBinaryTree()
	/*
	   Binary Tree
	  -----------------------
	       5
	     /   \
	    7     4
	   /       \
	  1         2
	   \       /
	    2     5
	*/
	// Binary tree nodes
	tree.root = getTreeNode(5)
	tree.root.left = getTreeNode(7)
	tree.root.right = getTreeNode(4)
	tree.root.left.left = getTreeNode(1)
	tree.root.right.right = getTreeNode(2)
	tree.root.right.right.left = getTreeNode(5)
	tree.root.left.left.right = getTreeNode(2)
	// Display Tree elements
	tree.inorder(tree.root)
	var result bool = tree.isFoldable(tree.root.left, 
						tree.root.right)
	if result == true {
		fmt.Println("\n Foldable Tree")
	} else {
		fmt.Println("\n Not Foldable Tree")
	}
	/*
	         5
	       /   \
	      7     4
	     /       \
	    1         2
	     \       /
	      2     5
	       \
	        3  
	*/
	// Case 2
	tree.root.left.left.right.right = getTreeNode(3)
	tree.inorder(tree.root)
	result = tree.isFoldable(tree.root.left, tree.root.right)
	if result == true {
		fmt.Println("\n Foldable Tree")
	} else {
		fmt.Println("\n Not Foldable Tree")
	}
}

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