Postorder traversal of a Binary Tree

Overview

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

• Vist Left Subtree

• Visit Right Subtree

• Visit Root

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

Then postorder traversal would be

[4 2 5 6 3 1]

Program

Here is the program for the same

package main

import (
	"fmt"
)

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

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

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

	output := make([]int, 0)

	output = append(output, left...)

	output = append(output, right...)

	output = append(output, root.Val)
	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 := postorderTraversal(&root)
	fmt.Println(output)

}

Output

[4 2 5 6 3 1]