Many problems require we visit the nodes of a tree in a systematic way: tasks such as counting how many nodes exist or finding the maximum element. Three different methods are possible for binary trees: preorder, postorder, and in-order, which all do the same three things: recursively traverse both the left and right subtrees and visit the current node. The difference is when the algorithm visits the current node:
- preorder: Current node, left subtree, right subtree (DLR)
- postorder: Left subtree, right subtree, current node (LRD)
- in-order: Left subtree, current node, right subtree (LDR)
- levelorder: Level by level, from left to right, starting from the root node.
Visit means performing some operation involving the current node of a tree, like incrementing a counter or checking if the value of the current node is greater than any other recorded.