Visualizer › Trees
Preorder Traversal
Visits the node first, then its left subtree, then its right subtree.
How it works
- Root → Left → Right.
- Used to copy or serialize a tree.
- Iterative version uses a stack (push right, then left).
Complexity
- Best time: O(n)
- Average time: O(n)
- Worst time: O(n)
- Extra space: O(h)
Code (Python)
def preorder(node, out):
if node:
out.append(node.val)
preorder(node.left, out)
preorder(node.right, out)Practise: Trees problems