In-Order Traversal of a Binary Search Tree
Output so far
Nothing yet.
- Not reached
- On the stack
- Current
- Visited
1/19
In-Order walk over 7 values, 3 levels deep.
Settings
More options
How it was built
In-Order
- 1
stack = []; node = root - 2
while node or stack: - 3
while node: - 4
stack.push(node) - 5
node = node.left - 6
node = stack.pop() - 7
visit(node) - 8
node = node.right
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.