Top view of binary tree using recursion in golang
Go program for Top view of binary tree using recursion. Here more information.
package main
import "fmt"
/*
Go program for
Top view of binary tree using dfs
*/
// Binary Tree Node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
// Set node value
return &TreeNode {data,nil,nil}
}
type BinaryTree struct {
root * TreeNode
level int
}
func getBinaryTree() * BinaryTree {
// Set the initial value of root
return &BinaryTree {nil,0}
}
// Print left side top nodes including root
func(this *BinaryTree) printleftSide(node * TreeNode, depth int) {
if node != nil {
if this.level < depth {
// Print the resultant node
fmt.Print(" ", node.data)
this.level = depth
}
// Recursively
// Visit left subtree
this.printleftSide(node.left, depth + 1)
// Visit right subtree
this.printleftSide(node.right, depth - 1)
}
}
// Print right side top nodes
func(this *BinaryTree) printRightSide(node * TreeNode, depth int) {
if node != nil {
if this.level < depth {
// Print the resultant node
fmt.Print(" ", node.data)
this.level = depth
}
// Recursively
// First visit right subtree
this.printRightSide(node.right, depth + 1)
// Then
// Visit left subtree
this.printRightSide(node.left, depth - 1)
}
}
// This is handle the request of printing top view
func(this *BinaryTree) topView() {
this.level = -1
this.printleftSide(this.root, 0)
this.level = 0
this.printRightSide(this.root, 0)
}
func main() {
// Create new tree
var tree * BinaryTree = getBinaryTree()
/*
Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
/ \
7 8
\
9
\
10
*/
// Construct binary tree
tree.root = getTreeNode(1)
tree.root.left = getTreeNode(2)
tree.root.right = getTreeNode(3)
tree.root.right.right = getTreeNode(6)
tree.root.right.left = getTreeNode(5)
tree.root.left.left = getTreeNode(4)
tree.root.left.left.left = getTreeNode(7)
tree.root.right.left.right = getTreeNode(8)
tree.root.right.left.right.right = getTreeNode(9)
tree.root.right.left.right.right.right = getTreeNode(10)
// Display top view
tree.topView()
}
Output
1 2 4 7 3 6 10
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