Traversal

“Traverse” just means visiting every node once, in some defined order. There are three common orders, and they all follow the same left/right/root pattern — just rearranged:

– In-order (left, node, right) — visits every value in sorted order. This is the one to reach for when you want the data back out sorted.

– Pre-order (node, left, right) — visits parents before their children. Useful for copying a tree, since you always create a node before its children.

– Post-order (left, right, node) — visits children before their parent. Useful for deleting a tree safely, since you can remove each node only after its children are already gone.

Notice that in-order is the only one of the three that comes out sorted (20, 30, 40, 50, 70) — that’s a direct result of the same left-smaller, right-larger rule the whole tree is built on.