Sponsored
Sponsored
The recursive approach naturally aligns with the definition of preorder traversal: visit the root first, then recursively traverse the left subtree, followed by the right subtree.
Time Complexity: O(N) where N is the number of nodes, as each node is visited once. Space Complexity: O(N) in the worst case due to recursion stack space.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7def preorderTraversal(root):
8 result = []
9 def preorder(node):
10 if not node:
11 return
12 result.append(node.val)
13 preorder(node.left)
14 preorder(node.right)
15 preorder(root)
16 return resultPython makes use of a nested helper function for the recursive traversal, adding node values directly to a list. The solution is concise and functional.
The iterative approach replaces the recursive call stack with an explicit stack. Nodes are processed in preorder, using a stack to maintain traversal state.
Time Complexity: O(N), since each node is visited once. Space Complexity: O(N), for the stack used to store nodes.
1function
JavaScript achieves preorder traversal iteratively using an array to simulate the stack. This approach offers flexibility and error resilience in managing deep trees.