Binary Tree Inorder Traversal

Problem

• Given the root of a binary tree, return the inorder traversal of its nodes' values.

Reflections

There is probably a more efficient way to do it but all of the solutions posted had worse space complexity than mine.

Go Solution

func inorderTraversal(root *TreeNode) []int {
	var res []int
	
	return traverse(root, res)
}

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

    res = traverse(root.Left, res)
	res = append(res, root.Val)
	res = traverse(root.Right, res)

	return res
}

Performance

• Runtime beats: 100%
• Memory beats: 82%

Complexity

• Time: O(n)
• Space: O(n)