Tree Algorithms

Four ways to walk a binary search tree and one way to search it, one page each. Rebuild the tree on any page and see what values that arrive already sorted do to its height.

O(n)
In-order traversal
Left, node, right, and the values come out sorted.
O(n)
Pre-order traversal
Visit the node, then its left and right subtrees.
O(n)
Post-order traversal
Both subtrees first, the node itself last.
O(n)
Level-order traversal
One level at a time, with a queue.
O(log n)
BST search
Compare, go left or right, repeat.

Developed by Akif Akkaya