589. N-ary Tree Preorder Traversal
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 73.5%
Problem Breakdown
The problem requires us to perform a preorder traversal on an n-ary tree and return the values of its nodes in that order. In a preorder traversal, we visit the root node first, then recursively visit each child from left to right.
Inputs:
root: The root node of the n-ary tree.
Outputs:
- A list containing the values of the nodes in preorder traversal order.
Implicit Constraints or Tricky Edge Cases:
- The tree can be empty (
rootisNone). - Nodes can have zero or more children.
- The number of nodes is between 0 and 10,000.
- Each node’s value is between 0 and 10,000.
Intuition
A brute-force approach would involve recursively visiting each node and its children. However, this approach can be inefficient in terms of space complexity due to the call stack depth, especially for deep trees.
The key insight is to use an iterative approach with a stack to simulate the recursive behavior. This avoids the overhead of function calls and reduces the risk of hitting the maximum recursion depth limit.
Approach
- Initialize: Start by checking if the
rootisNone. If it is, return an empty list since there are no nodes to traverse. - Stack Setup: Use a stack to keep track of nodes to visit. Initialize the stack with the
rootnode. - Traversal Loop:
- While the stack is not empty, pop the top node from the stack and add its value to the result list.
- Push all children of the current node onto the stack in reverse order (rightmost child first) so that they are processed in left-to-right order when popped.
- Return Result: Once the stack is empty, return the result list containing the preorder traversal.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited exactly once.
- Space Complexity: O(n) in the worst case, when the tree is a straight line (i.e., each node has only one child). This occurs because all nodes are stored in the stack at some point.
Solution
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
def preorder(root: 'Node') -> List[int]:
if root is None:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Add children to the stack in reverse order
for child in reversed(node.children):
stack.append(child)
return result
Edge Cases Handled
- Empty Tree: If
rootisNone, the function returns an empty list immediately. - Single Node Tree: If the tree consists of only one node, that node’s value is returned in a single-element list.
- Deep Trees: The iterative approach handles deep trees efficiently without hitting recursion limits.
- Nodes with No Children: Nodes with no children are simply added to the result list and do not affect the traversal order.