❔ ✅ comprehension questions for a LeetCode puzzle
I am analysing the following LC solution (the iterative one)
https://leetcode.com/problems/n-ary-tree-preorder-traversal/solutions/3185068/iteratively-and-recursively-method-with-description-c/
I have a questions with regards to a couple of lines in this code.
1. It's "Stack.Push(root)" instead of "result.Add(root)". I get that the root node shall be added to the return array, but I still do not understand why the stack comes out here.
2. And the few lines below 1., it's "result.Add(currentNode.val), instead of "Stack.Push(currentNode.val)". Here I am still confused how the stack and the List have been used interchangeably (or non-interchangeably).
3. The same goes for the line "stack.Push(currentNode.children[i])" , instead of "result.Add(currentNode.val)". Why is the stack push here?
It would be great if anyone could explain to me a bit about those questions.
LeetCode
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
5 Replies
It's "Stack.Push(root)" instead of "result.Add(root)". I get that the root node shall be added to the return array, but I still do not understand why the stack comes out here.If you didn't add the root node to the stack, when you enter the
while (stack.Count>0) loop and start processing items from the stack, the stack would be empty!
In other words, the stack contains a list of things you haven't yet processed but need to. The first thing you process is the root node, so you start by adding that to the stack, and then immediately popping it off and processing it. Sure, you could just process the root node directly without pushing/popping it onto/off the stack, but you end up duplicating the processing code.
Actually, I think all of your questions stem from the gap in understanding
The stack is a list of nodes that you've discovered but haven't yet processed. The list is a list of things which you've processed
The general pattern of using a stack in this way is a common way to handle recursively walking a tree (or a directory structure, etc). The idea is that you've got a stack of nodes you haven't processed yet. Pop a node off the stack, process it, then add all of its children to the stack. Then pop the first of those children back off the stack, process it, push any of its children on, and so on. That way you end up doing a depth-first walk of the tree -- you first visit a node, then its first child, then that child's first child, etc, until you finish that branch of the tree; then you visit the node's second child, and so on
(You can use a queue rather than a stack, which gives you a breadth-first traversal)
In this question, the "processing" step just means adding it to the list of results. Adding the parent node to the list of results before we visit its children means that we get a pre-order traversal. (Adding a parent node after processing its children would give us post-order, and adding it in between processing its children would give us in-order)Thank you so much for the explanation in depth 🙂 Yes, I do have a big gap in understanding all this correctly. I am not sure if trying to solve a few hundreds of LC help me or not, but I will not give up on it 🙂
May I ask one more question with regards to this LC puzzle?
If I look at any recursion solutions posted on LC, there is no Stack used there. They are like "you do list.Add(node) then call the function recursively". But if I look at a couple of iterative solutions, the root node is always pushed to Stack (stk.Push(root)) instead of list.Add. Is it because the node needs to be popped later (like Node node = stk.Pop()) in the loop? I am still wondering why the Stack is absent in the recursive solutions submitted on LC:
In a recursive solution, you use the function call stack as the stack. So the children to process next are stored as variables in the stack frame of the function. When you move to an iterative solution, you turn the implicit call stack into an explicit stack object
If you debug into a recursive solution in VS, then break the debugger and look at the call stack pane, you'll see all of the stack frames. You can click on them and inspect the local variables stored in each
It's very similar to debugging into an interactive solution and inspecting the stack object
(and if you don't know how the function call stack works, this is your opportunity to read up on it)
Ahhhh ok thank you so much for the great explanation again 🙂 I got it why the function call stack comes out in a recursive solution.
I think I will use the proper IDE for future LC puzzles, so I can see the debugger better (and I think I will learn much much better than I do with the LC's own editor).
And I will read up on the function call stack
Was this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.