Posted on by Kalkicode
Code Binary Tree

Transform linked list into complete binary tree in golang

Go program for Implement complete binary tree using linked list. Here problem description and other solutions.

package main
import "fmt"
/*
    Go program for
    Inplace construct linked list into complete binary tree
*/
// Linked list node
type LinkNode struct {
	data int
	right * LinkNode
	left * LinkNode
}
func getLinkNode(data int) * LinkNode {
	// return new LinkNode
	return &LinkNode {
		data,
		nil,
		nil,
	}
}
type BinaryTree struct {
	root * LinkNode
}
func getBinaryTree() * BinaryTree {
	// return new BinaryTree
	return &BinaryTree {
		nil,
	}
}
// Adding new node at beginning of linked list
func(this *BinaryTree) addNode(data int) {
	// Create new node
	var node * LinkNode = getLinkNode(data)
	// Connect current node to previous root
	node.right = this.root
	this.root = node
}
// Display linked list element
func(this BinaryTree) linkedList() {
	if this.root == nil {
		return
	}
	var temp * LinkNode = this.root
	// iterating linked list elements
	for (temp != nil) {
		fmt.Print(temp.data, " → ")
		// Visit to right node
		temp = temp.right
	}
	fmt.Println("NULL")
}
func(this BinaryTree) makeCompleteBinaryTree() {
	if this.root == nil {
		// When tree is empty
		return
	}
	// Auxiliary variables
	var head * LinkNode = this.root
	var current * LinkNode = this.root
	var front * LinkNode = nil
	// We can use to solve this problem using queue but
	// queue can be implemented by using linked list
	for (current != nil || head != nil) {
		// Get next node
		front = head.right
		if current != nil {
			// When left and right child possible of head node
			// Get first child
			current = current.right
			if current != nil {
				// When node exist
				// Add left child
				head.left = current
				// Get second child
				current = current.right
			}
			// Add right child
			head.right = current
		} else {
			// When no child
			head.left = nil
			head.right = nil
		}
		head = front
	}
}
// Display preorder of binary tree
func(this BinaryTree) preorder(node * LinkNode) {
	if node != nil {
		// Display node value
		fmt.Print("  ", node.data)
		// Visit left subtree
		this.preorder(node.left)
		// Visit right subtree
		this.preorder(node.right)
	}
}
// Display inorder of binary tree
func(this BinaryTree) inorder(node * LinkNode) {
	if node != nil {
		// Visit left subtree
		this.inorder(node.left)
		// Display node value
		fmt.Print("  ", node.data)
		// Visit right subtree
		this.inorder(node.right)
	}
}
// Display postorder of binary tree
func(this BinaryTree) postorder(node * LinkNode) {
	if node != nil {
		// Visit left subtree
		this.postorder(node.left)
		// Visit right subtree
		this.postorder(node.right)
		// Display node value
		fmt.Print("  ", node.data)
	}
}
func main() {
	var task * BinaryTree = getBinaryTree()
	// Linked list
	// 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → NULL
	task.addNode(10)
	task.addNode(9)
	task.addNode(8)
	task.addNode(7)
	task.addNode(6)
	task.addNode(5)
	task.addNode(4)
	task.addNode(3)
	task.addNode(2)
	task.addNode(1)
	fmt.Print("\n Linked list node \n ")
	task.linkedList()
	task.makeCompleteBinaryTree()
	/*
	           1
	          / \
	         /   \ 
	        /     \
	       2       3
	      / \     / \
	     /   \   /   \
	    4     5 6     7 
	   / \   /
	  8   9 10  
	  -------------------------
	  Construct binary tree
	*/
	fmt.Println("\n After build complete binary tree ")
	fmt.Println(" Preorder ")
	task.preorder(task.root)
	fmt.Println("\n Inorder ")
	task.inorder(task.root)
	fmt.Println("\n Postorder ")
	task.postorder(task.root)
}

Output

 Linked list node 
 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → NULL

 After build complete binary tree 
 Preorder 
  1  2  4  8  9  5  10  3  6  7
 Inorder 
  8  4  9  2  10  5  1  6  3  7
 Postorder 
  8  9  4  10  5  2  6  7  3  1

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