Concept

How does recursion support tree traversal?

Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1

"Finally, it’s worth mentioning that all of these traversal methods make elegant use of recursion. Recursion is a way of taking a large problem and breaking it up into similar, but smaller, sub-problems. Then, each of those subproblems can be attacked in the same way as you attacked the larger problem: by breaking them up into subproblems. All you need is a rule for eventually stopping the “breaking up” process by actually doing something. Every time one of these traversal processes treats a left or right child as a subtree, they are “recursing” by re-initiating the whole traversal process on a smaller tree. Pre-order traversal, for instance, after visiting the root, says, “okay, let’s pretend we started this whole traversal thing with the smaller tree rooted at my left child. Once that’s finished, wake me up so I can similarly start it with my right child.” Recursion is a very common and useful way to solve certain complex problems, and trees are rife with opportunities."

Related Ideas

How does recursion support tree traversal? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm