Binary Tree Inorder Traversal

1. Problem Description

Given the root root of a binary tree, return its inorder traversal.

2. Approach

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

3. Implementation

3.1. Recursion

package main

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

func inorderTraversal(root *TreeNode) []int {
	res := make([]int, 0)
	inordered(root, &res)
	return res
}

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

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

3.2. Color Marking

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

const (
    ColorWhite = 0
    ColorGray = 1
)

type Node struct {
    node *TreeNode
    color int
}

func inorderTraversal(root *TreeNode) []int {
    stack := make([]*Node, 0)
    stack = append(stack, &Node{node:root, color: ColorWhite})
    res := make([]int, 0)
    for len(stack) > 0 {
        pop := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if pop.node == nil {
            continue
        } 
        if pop.color == ColorWhite {
            stack = append(stack, &Node{node:pop.node.Right, color:ColorWhite})
            stack = append(stack, &Node{node:pop.node, color:ColorGray})
            stack = append(stack, &Node{node:pop.node.Left, color:ColorWhite})
        }else {
            res = append(res, pop.node.Val)
        }
    }
    return res
}

4. References

• Color Marking: A General and Concise Tree Traversal Method - LeetCode