N-ary Tree PreOrder Traversal

Title: N-ary Tree Preorder Traversal Source: leetcode.com

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

For example, given a 3-ary tree:

N-ary Tree

A 3-ary tree

Return its preorder traversal as: [1,3,5,6,2,4].

Note:

Recursive solution is trivial, could you do it iteratively?

You could find another explanation/ problem related to Preorder Traversal here.

Java solution (Recursive)

If you think closely about the recursive solution, what we are essentially doing is…
While parsing current node, we first add it’s value to the result list and then move on to each child turn by turn, in left to right order, parsing it as the next current node.

So, to get to an iterative solution, what we need to have is a stack where children to current node could be placed for parsing next and the catch is that they need to be put in reverse order so that the left most child becomes first candidate for parsing.

Python solution (Iterative)

N-ary Tree PreOrder Traversal
Rate this post

Leave a Reply