Pre-order binary tree traversal is a technique used to visit all the nodes of a binary tree in the following order: First, the root node of the current tree is visited, then all nodes in the left subtree are visited in pre-order fashion, and finally all the nodes in the right subtree are visited in pre-order fashion. The animated examples discussed in the next section will make the definition more clear.
Animation of Pre-Order Binary Tree Traversal
Let’s consider the below binary tree and apply the pre-order tree traversal technique:
Node A is the root node of the binary tree. We need to visit this node before visiting all the nodes under it’s left and right subtrees in pre-order fashion. Visited nodes will be coloured in green.
Now we need to visit all the nodes under the left subtree of node A i.e., subtree with root as node B in pre-order fashion. We apply the same logic again i.e, first visit the subtree’s root node (B), then visit all nodes in left subtree under node B, and then visit all nodes in right subtree under node B. So we visit node B, left subtree of node B contains a singe node D so we just visit that node and finally visit node E.
Now that all the nodes under the left subtree of node A are visited, we need to visit all nodes under the right subtree of node A in pre-order fashion.
This is the order in which we visited all the nodes: A, B, D, E, C, F, G.
Recursive Implementation
Below is the implementation of a function which takes in the root node of a binary tree and traverses all the nodes in Pre-Order fashion. It uses recursion technique which is much simpler and straightforward than the iterative version.
Iterative Implementation