5.1: Traversal
( \newcommand{\kernel}{\mathrm{null}\,}\)
selected template will load here
This action is not available.
( \newcommand{\kernel}{\mathrm{null}\,}\)
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:
Note
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.