Skip to main content

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




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