Check for continuous binary tree in golang
Go program for Check for continuous binary tree. Here problem description and explanation.
package main
import "fmt"
/*
Go program for
Check if binary tree is continuous 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) absValue(num int) int {
if num < 0 {
return -num
}
return num
}
// Check tree is continuous or not
func(this BinaryTree) isContinuous(node * TreeNode) bool {
if node != nil {
if (node.left != nil &&
this.absValue(node.data - node.left.data) != 1) ||
(node.right != nil &&
this.absValue(node.data - node.right.data) != 1) {
// Case
// When fail continuous tree rule
return false
}
if this.isContinuous(node.left) &&
this.isContinuous(node.right) {
return true
}
// When node value is not satisfied
// continuous tree properties
return false
}
return true
}
func main() {
// Create new tree
var tree * BinaryTree = getBinaryTree()
/*
Binary Tree
------------
5
/ \
4 4
/ / \
3 5 3
\
2
*/
// Add tree node
tree.root = getTreeNode(5)
tree.root.left = getTreeNode(4)
tree.root.right = getTreeNode(4)
tree.root.left.left = getTreeNode(3)
tree.root.right.right = getTreeNode(3)
tree.root.right.left = getTreeNode(5)
tree.root.left.left.right = getTreeNode(2)
if tree.isContinuous(tree.root) == true {
fmt.Println("Continuous Tree ")
} else {
fmt.Println("Not Continuous Tree ")
}
// Case 2
/*
5
/ \
4 4
/ / \
3 5 3
\
1 <--- change value
*/
tree.root.left.left.right.data = 1
if tree.isContinuous(tree.root) == true {
fmt.Println("Continuous Tree ")
} else {
fmt.Println("Not Continuous Tree ")
}
}
Output
Continuous Tree
Not Continuous Tree
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