Tree Algorithms
A binary search tree you can rebuild at will. Walk it in four different orders or search it for a value, and see what happens to the height when the inserts arrive already sorted.
Output so far
Nothing yet.
- Not reached
- On the stack
- Current
- Visited
Speed
Step 1 of 19
In-order walk over 7 values, 3 levels deep.
Counters
- Visited
- 0/7
- On the stack
- 0
- Tree height
- 3
- Nodes
- 7
Settings
Walk
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) |
h is the tree height and w its widest level. Build the same values with Sorted inserts and h becomes n, which is what balancing exists to prevent.