Inorder traversal of a Binary Tree

Overview

In the inorder traversal of a binary tree, we follow the below order

• Vist Left Subtree

• Visit Root

• Visit Right Subtree

For example, let’s say we have below binary tree

Then inorder traversal would be

[4 2 1 5 3 6]

Program

Here is the program for the same

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	left := inorderTraversal(root.Left)
	right := inorderTraversal(root.Right)

	output := make([]int, 0)

	output = append(output, left...)
	output = append(output, root.Val)
	output = append(output, right...)
	return output

}

func main() {
	root := TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Left.Left = &TreeNode{Val: 4}
	root.Right = &TreeNode{Val: 3}
	root.Right.Left = &TreeNode{Val: 5}
	root.Right.Right = &TreeNode{Val: 6}

	output := inorderTraversal(&root)
	fmt.Println(output)

}

Output

[4 2 1 5 3 6]