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.

Any doubts? Please feel free to drop in your comments..!