Preorder tree traversal in Python

In this tutorial, we will learn one of the three ways of Depth-first searches that is the Preorder traversal of a tree data structure with recursion in Python. It is also known as NLR(Node, Left, Right) algorithm. Recursion is the easiest way to solve tree traversal problems. I recommend you to get familiar with recursion.

Let’s create a binary tree and learn to traverse it.

```class Tree:
def __init__(node,value):
node.value = value
node.right = None
node.left = None
def create_node(node,value):
if (node.value is None):
node.value = value
else:
if( value < node.value ):
if (node.left is None):
node.left = Tree(value)
else:
node.left.create_node(value)
elif( value > node.value ):
if ( node.right is None):
node.right = Tree(value)
else:
node.right.create_node(value)
Root = Tree(5)
Root.create_node(7)
Root.create_node(9)
Root.create_node(2)
Root.create_node(4)
Root.create_node(3)
Root.create_node(8)
Root.create_node(1)
Root.create_node(6)```

Preorder traversal using Recursion in Python

```def Preorder( node, Root ):

if( Root is None ):
return

print(Root.value,end = ' ')
node.Preorder(Root.left)
node.Preorder(Root.right)```
• Access the value of the current node.
• Traverse the left subtree recursively.
• Traverse the right subtree recursively.

The order of the Inorder traversal is 5 2 1 4 3 7 6 9 8.

Explanation:

• Firstly we created a binary tree with 9 nodes and performed preorder traversal using recursive function.
• If a node is not empty, print the value of the node, recursively traverse the left subtree and then the right subtree.
• If a node is empty, return to the calling function, that is the parent node and continue.

Note: If we traverse the parent node, then the right subtree and at last the left subtree, then such a traversal is called reverse preorder traversal.

Here is how the complete code should look like

```class Tree:
def __init__(node,value):
node.value = value
node.right = None
node.left = None
def create_node(node,value):
if (node.value is None):
node.value = value
else:
if( value < node.value ):
if (node.left is None):
node.left = Tree(value)
else:
node.left.create_node(value)
elif( value > node.value ):
if ( node.right is None):
node.right = Tree(value)
else:
node.right.create_node(value)
def Preorder( node, Root ):

if( Root is None ):
return
print(Root.value,end = ' ')
node.Preorder(Root.left)

node.Preorder(Root.right)
Root = Tree(5)
Root.create_node(7)
Root.create_node(9)
Root.create_node(2)
Root.create_node(4)
Root.create_node(3)
Root.create_node(8)
Root.create_node(1)
Root.create_node(6)
print('Preorder traversal :',end = '')
Root.Preorder(Root)
```

Output:

`Preorder traversal :5 2 1 4 3 7 6 9 8`

Also, read Postorder traversal and level order traversal in Python.