Problem List

N-ary Tree Preorder Traversal

May 30, 2025 • Go • stack, tree, depth first search • easy

Problem

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

Reflections

Memorized at this point.

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

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
}

LeetCode Problem Link