Insertion in binary search tree without recursion in golang

Go program for Insertion in binary search tree without recursion. Here problem description and other solutions.

package main
import "fmt"
// Go program for
// iterative insert in binary search tree
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 element
func(this *BinarySearchTree) addNode(data int) {
	// Create a new node
	var node * TreeNode = getTreeNode(data)
	if this.root == nil {
		// When adds a first node in bst
		this.root = node
	} else {
		var find * TreeNode = this.root
		// Add new node to proper position
		for (find != nil) {
			if find.data >= data {
				if find.left == nil {
					// When left child empty
					// So add new node here
					find.left = node
					return
				} else {
					// Otherwise
					// Visit left sub-tree
					find = find.left
				}
			} else {
				if find.right == nil {
					// When right child empty
					// So add new node here
					find.right = node
					return
				} else {
					// Visit right sub-tree
					find = find.right
				}
			}
		}
	}
}
// 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.addNode(10)
	tree.addNode(4)
	tree.addNode(3)
	tree.addNode(5)
	tree.addNode(15)
	tree.addNode(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







© 2021, kalkicode.com, All rights reserved