Golang – Inorder Tree Traversal

Golang – Inorder Tree Traversal

Here in this article, we shall discuss steps and different approach of implementing Inorder tree traversal. You can get the inorder tree traversal in java in our article Inorder Tree Traversal (DFS) in java. There are two ways, iterative and recursive for inorder tree traversal. We follow below steps for traversal

1) Traverse the left subtree, i.e., call Inorder(left-subtree)
2) Visit the root.
3) Traverse the right subtree, i.e., call Inorder(right-subtree)

Inorder Traversal of above tree is 70, 40, 20, 50, 10, 30, 60

Time Complexity: O(n)

Recursive solution for Inorder Tree Traversal :

Algorithm for recursive solution is

1) Traversal left node i.e inorder(root.left) 
2) Print root node
3) Traversal right node i.e inorder(root.right)

Code for recursive solution

package main

import "fmt"

type Node struct {
	val   int
	left  *Node
	right *Node
}

func InorderRecursive(root *Node) {
	if root == nil {
		return
	}

	InorderRecursive(root.left)
	fmt.Printf("%d ", root.val)
	InorderRecursive(root.right)
}

func main() {
	/*
				10
			   /  \
			 20	   30
			/ \      \
		   40  50     60
		  /
		 70
	*/

	root := &Node{10, nil, nil}
	root.left = &Node{20, nil, nil}
	root.right = &Node{30, nil, nil}
	root.left.left = &Node{40, nil, nil}
	root.left.right = &Node{50, nil, nil}
	root.right.right = &Node{60, nil, nil}
	root.left.left.left = &Node{70, nil, nil}

	fmt.Println("Inorder Traversal - recursive solution : ")
	InorderRecursive(root)
}

Output

Inorder Traversal - recursive solution :
70 40 20 50 10 30 60

Iterative solution for Inorder Traversal

To implement iterative solution for Inorder Traversal, we will be using Stack data structure. Use “go get github.com/emirpasic/gods/stacks/arraystack” to get stack.

Algorithm for iterative solution is

1) create stack and initialize currentNode as root.
2) while stack is not empty or currentNode not equals to Null, do the following
   - if currentNode != Null, push currentNode to stack and assign currentNode = currentNode.left
   - else pop top node from stack, print node data and assign currentNode = stack[top].right
package main

import (
	"fmt"

	"github.com/emirpasic/gods/stacks/arraystack"
)

type Node struct {
	val   int
	left  *Node
	right *Node
}

func InorderIterative(root *Node) {
	if root == nil {
		return
	}

	temp := root
	stack := arraystack.New()
	for stack.Size() > 0 || temp != nil {
		if temp != nil {
			stack.Push(temp)
			temp = temp.left
		} else {
			obj, _ := stack.Pop()
			temp = obj.(*Node)
			fmt.Printf("%d ", temp.val)
			temp = temp.right
		}
	}
}

func main() {
	/*
				10
			   /  \
			 20	   30
			/ \      \
		   40  50     60
		  /
		 70
	*/

	root := &Node{10, nil, nil}
	root.left = &Node{20, nil, nil}
	root.right = &Node{30, nil, nil}
	root.left.left = &Node{40, nil, nil}
	root.left.right = &Node{50, nil, nil}
	root.right.right = &Node{60, nil, nil}
	root.left.left.left = &Node{70, nil, nil}

	fmt.Println("Inorder Traversal - iterative solution : ")
	InorderIterative(root)
}

Output

Inorder Traversal - iterative solution :
70 40 20 50 10 30 60

Stay tuned for more updates and tutorials !!!

Leave a Reply

Your email address will not be published. Required fields are marked *