Preorder Traversal
Learn more about preorder traversal and how to code it iteratively and recursively.
We'll cover the following...
The preorder traversal method
Preorder tree traversal is very useful and efficient for copying tree-like data structures. To perform preorder tree traversal, we use a method like preOrder() that will take the node object as a parameter and call itself.
Iterative preorder traversal
Let’s look at an iterative preorder tree traversal code snippet, which will give us a clear picture of how we can implement our algorithm. This shows how we can traverse the tree without recursion.
We start spanning the tree with the root node; after that, we visit the left subtree, and next, we visit the right subtree. Each subtree is also visited in the preorder way. That means it starts from the root of the subtree and then goes to the left subtree, and the process continues until we reach a leaf node.
The traversal pattern clearly tells us that this tree traversal is a good candidate for recursion. After visiting the root node, we can recursively visit the left subtree and then visit the right subtree again.
Still, recursion is not ...