Binary Tree Preorder, Inorder, and Postorder Traversal

1. Problem Description

Print all nodes of a binary tree in preorder, inorder, and postorder respectively.

2. Approach

1. Approach 1
   • Recursion
2. Approach 2
   • Color marking

3. Implementation

package main

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

/**
 *
 * @param root TreeNode the root of binary tree
 * @return two-dimensional integer array
 */
func threeOrders(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}

	res := make([][]int, 0)

	pre := make([]int, 0)
	preOrder(root, &pre)
	res = append(res, pre)

	mid := make([]int, 0)
	midOrder(root, &mid)
	res = append(res, mid)

	post := make([]int, 0)
	postOrder(root, &post)
	res = append(res, post)

	return res
}

func postOrder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}

	postOrder(root.Left, res)
	postOrder(root.Right, res)
	*res = append(*res, root.Val)
}

func midOrder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}

	midOrder(root.Left, res)
	*res = append(*res, root.Val)
	midOrder(root.Right, res)
}

func preOrder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}

	*res = append(*res, root.Val)
	preOrder(root.Left, res)
	preOrder(root.Right, res)
}

4. References

• Binary Tree Preorder, Inorder, and Postorder Traversal - NowCoder
• Color Marking: A General and Concise Tree Traversal Method - LeetCode