N-ary Tree Preorder Traversal

Problem

• Given the root of an n-ary tree, return the preorder traversal of its nodes' values.

Reflections

Memorized at this point.

Go Solution

func preorder(root * Node)[]int {
  var res []int
  var dfs func(node * Node)
  dfs = func(node * Node) {
    if node == nil {
      return
    }

    res = append(res, node.Val)
    for _, child := range(node.Children) {
      dfs(child)
    }
  }

  dfs(root)
  return res
}

Performance

• Runtime beats: 60%
• Memory beats: 80%

Complexity

• Time: O(n)
• Space: O(n + h) - h is height of tree, if its nothing more than a degenerate linked list