LeetCode-in-All

94. Binary Tree Inorder Traversal

Easy

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

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Example 2:

Input: root = []

Output: []

Example 3:

Input: root = [1]

Output: [1]

Example 4:

Input: root = [1,2]

Output: [2,1]

Example 5:

Input: root = [1,null,2]

Output: [1,2]

Constraints:

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution

# Definition for a binary tree node.
#
# defmodule TreeNode do
#   @type t :: %__MODULE__{
#           val: integer,
#           left: TreeNode.t() | nil,
#           right: TreeNode.t() | nil
#         }
#   defstruct val: 0, left: nil, right: nil
# end

defmodule Solution do
  @spec inorder_traversal(root :: TreeNode.t | nil) :: [integer]
  def inorder_traversal(root) do
    []
    |> in_walk(root, &[&2 | &1])
    |> Enum.reverse()
  end

  @spec in_walk(acc, nil | TreeNode.t, (acc, val -> acc)) :: acc
        when acc: any, val: any
  defp in_walk(acc, nil, _fun), do: acc

  defp in_walk(acc, node, fun) do
    acc
    |> in_walk(node.left, fun)
    |> fun.(node.val)
    |> in_walk(node.right, fun)
  end
end