N-ary Tree Preorder Traversal

Description

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

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

 

Follow up:

Recursive solution is trivial, could you do it iteratively?

 

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

 

Constraints:

• The height of the n-ary tree is less than or equal to 1000
• The total number of nodes is between [0, 10^4]

Solution(javascript)

// Recursive
// const preorder = function (root) {
//   let acc = []
//   const aux = (node) => {
//     console.log(acc)
//     if (!node) {
//       return acc
//     }
//     acc.push(node.val)
//     if (node.children) {
//       node.children.forEach((child) => {
//         acc = aux(child)
//       })
//     }
//     return acc
//   }
//   return aux(root)
// }

// Iterative

const preorder = (root) => {
  const result = []
  const stack = []
  if (root) {
    stack.push(root)
  }
  while (stack.length > 0) {
    const node = stack.pop()
    result.push(node.val)
    if (node.children) {
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push(node.children[i])
      }
    }
  }
  return result
}


preorder({
  val: 1,
  children: [{
    val: 2,
  }],
})