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.
1#
In C, we use an array to simulate a stack, manually pushing and popping nodes while traversing the tree. Nodes are visited and added to the result list in prenode order.