Thread by @Iampatelajeet

"429. N-ary Tree Level Order Traversal", today's @LeetCode challenge explained with DFS and BFS methods.

A thread 🧵
#100daysOfCode
#leetcode

@LeetCode Problem Statement-
Given an n-ary tree, return the level order 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).

@LeetCode Understanding the problem-
Usually, we're given tree problems which has left and right child but here is something different. For any node, it's child are given in form of node arrays. It means now any node can have more than 2 child also.
We've to find level order traversal.

@LeetCode Intuition-
At first sight, it looks a bit complex but when you observe, it's really simple and very similar to standard BST. We can simply apply standard BFS & DFS methods to solve this problem.

Let's see solutions.

@LeetCode Approach 1: BFS
-> Push current node in queue.
-> Traverse queue,
-> Pick front node from queue, add it's child to queue
and current node to answer array.
-> Repeat the process for its child.
Time Complexity: O(n)
Auxiliary Space: O(n)

@LeetCode Approach 2: DFS
-> Apply standard method, pass one extra parameter level
-> Add the current node to answer at it's level, call function for it's child.
Time Complexity: O(n)
Auxiliary Space: O(n)

@LeetCode Approach 2.1, Space Optimized
In the above idea, we used map to maintain level and then copied to answer. We can do this without map, by simply increasing size of answer when it becomes equal to level.
Time Complexity: O(n)
Auxiliary Space: O(n)

@LeetCode That's a wrap!

If you enjoyed this thread:

1. Follow me @Iampatelajeet for,
‍💻 Coding,
🌐 Case Studies,
👻 free ka gyaan,
🤖 tech stuffs and
😉 coding memes
2. RT is appreciated, share and let everyone be consistent. Start the challenge with me.

https://twitter.com/Iampatelajeet/status/1566620764304015362