Pre-Order Traversal of a Binary Tree
Output so far
Nothing yet.
- Not reached
- On the stack
- Current
- Visited
1/13
Pre-Order walk over 7 values, 3 levels deep.
Settings
More options
How it was built
Pre-Order
- 1
stack = [root] - 2
while stack: - 3
node = stack.pop() - 4
visit(node) - 5
push node.right - 6
push node.left
What Each Walk Is For
| Walk | What you get | Time | Extra space |
|---|---|---|---|
| In-Order | Values in sorted order | O(n) | O(h) |
| Pre-Order | Root before children, for copying a tree | O(n) | O(h) |
| Post-Order | Children before root, for freeing or evaluating | O(n) | O(h) |
| Level-Order | Shallowest nodes first, level by level | O(n) | O(w) |
| Search | One value, by comparing at each node | O(h) | O(1) |
Scroll the table sideways for the rest of the columns.
n is the number of values, h the height of the tree and w its widest level. Built from sorted values, the tree gets a height of n. Balanced trees exist to prevent that.