Swift Leetcode Series: N-ary Tree Preorder Traversal

Iterative + recursive = Leetcode 589

N-ary Tree Preorder Traversal (Leetcode 589) -

You can also read the full story on The Swift Nerd blog with the link above.

Problem Statement

Given the root of 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)

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 number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The height of the n-ary tree is less than or equal to 1000.

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

Solution

Recursive

The problem is fairly easy using the recursion. In preorder traversal of Binary trees, we first recursively traverse left subtrees, then the right ones. Here the children nodes are given in an array in level-order form. So we can traverse nodes in a for loop and recursively calling the traversal function on the current element. We create an output array to store the results and add the root first and finally after traversing the whole tree , simply return the output array.

Follow Up: Iterative

If we look carefully, all traversals(Pre-order, InOrder, Post-Order) are Depth-first searches on a Tree and tree are special kind of ancestral graphs. So we can use the Depth-first traversal on the tree using a stack and processing the nodes. The approach would be:-

1. Create an empty stack to store leaf nodes
2. Push the root node on to the stack.
3. Create an output array to store the elements processed
4. While stack is not empty, pop() elements from the stack, add to the output result, add child nodes in the reversed order.
5. Finally return the output array

Why do we need to add child nodes in the reversed order? Because it is given in the question that child nodes are in serialised in level order and since Stack is a LIFO structure, we need to add right nodes first and left nodes last to the stack, so that left nodes are the first to pop out. In Swift, We can directly call the reversed() on the array while in C++ we will have to traverse the iterator in reverse direction, and in python we can use the slicing operator( [: :-1] ).

Code

Complexity Analysis

Every element is traversed once. Due to recursion, the stack space would be O(h), where h is the max height of the tree. We can also say O(logn) because h is bounded by logn. In the Iterative approach as well, since we are using the stack which is same as recursive calls, space would be bounded by LogN.

Time = O(N)

Space = O(LogN)

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github