DSA Pre-order Traversal
Pre-order Traversal of Binary Trees
Advance purchase A variation of Depth First Search is traversal, in which a certain order is visited at each node. Go here to learn more about traversals of binary trees in general.
A Binary Tree’s pre-order traversal looks like this:
==== example mukavu ====
Advance purchase First, the root node must be visited. Next, a recursive pre-order traversal of the left subtree must be performed, and finally, a recursive pre-order traversal of the right subtree. It can be applied to prefix notation of an expression tree, generating a replica of the tree, etc.
Because the node is visited “before” the recursive pre-order traversal of the left and right subtrees, this traversal is “pre” order.
The pre-order traversal code looks like this:
Example
Python:
def preOrderTraversal(node):
if node is None:
return
print(node.data, end=", ")
preOrderTraversal(node.left)
preOrderTraversal(node.right)
As the Pre-order Traversal operates by first visiting, or printing, the current node (line 4), it calls the left and right child nodes recursively (lines 5 and 6). Therefore, node R is the first node to be printed.
Line 5 of the preOrderTraversal() method continues the recursive traversal of the left subtree; line 6 continues this traversal of the right subtree. ‘A’ and ‘C’ are the following nodes to be printed.
When node C’s left child (because C has no left child) is supplied as an argument, the argument node is None for the first time.
Calling C’s left child yields None the first time; hence, calling C’s right child likewise gives None. The recursive calls then proceed backward, printing D, the right child of A, as the next to be printed.
The remaining nodes in R’s right subtree are printed as a result of the code continuing to propagate back.
