Insertion in binary search tree using recursion in golang
Go program for Insertion in binary search tree using recursion. Here more information.
package main
import "fmt"
// Go program for
// Insertion in binary search tree by using recursion
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
// return new TreeNode
return &TreeNode {
data,
nil,
nil,
}
}
type BinarySearchTree struct {
root * TreeNode
}
func getBinarySearchTree() * BinarySearchTree {
// return new BinarySearchTree
return &BinarySearchTree {
nil,
}
}
// Insert a node element
func(this BinarySearchTree) addNode(node * TreeNode,
data int) * TreeNode {
if node != nil {
if node.data >= data {
// When new element is smaller or
// equal to current node
node.left = this.addNode(node.left, data)
} else {
// When new element is higher to current node
node.right = this.addNode(node.right, data)
}
// important to manage root node
return node
} else {
return getTreeNode(data)
}
}
// Display preorder
func(this BinarySearchTree) preorder(node * TreeNode) {
if node != nil {
// Display node value
fmt.Print(" ", node.data)
// Visit to left subtree
this.preorder(node.left)
// Visit to right subtree
this.preorder(node.right)
}
}
func(this BinarySearchTree) inorder(node * TreeNode) {
if node != nil {
// Visit to left subtree
this.inorder(node.left)
// Display node value
fmt.Print(" ", node.data)
// Visit to right subtree
this.inorder(node.right)
}
}
func(this BinarySearchTree) postorder(node * TreeNode) {
if node != nil {
// Visit to left subtree
this.postorder(node.left)
// Visit to right subtree
this.postorder(node.right)
// Display node value
fmt.Print(" ", node.data)
}
}
func main() {
var tree * BinarySearchTree = getBinarySearchTree()
/*
10
/ \
/ \
4 15
/ \ /
3 5 12
-------------
Build binary search tree
*/
tree.root = tree.addNode(tree.root, 10)
tree.addNode(tree.root, 4)
tree.addNode(tree.root, 3)
tree.addNode(tree.root, 5)
tree.addNode(tree.root, 15)
tree.addNode(tree.root, 12)
// Display tree nodes
fmt.Println("Preorder ")
tree.preorder(tree.root)
fmt.Println("\nInorder ")
tree.inorder(tree.root)
fmt.Println("\nPostorder ")
tree.postorder(tree.root)
}
Output
Preorder
10 4 3 5 15 12
Inorder
3 4 5 10 12 15
Postorder
3 5 4 12 15 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