Preorder Traversal of Binary Tree in Python

In this tutorial, we will cover the preorder traversal ( DLR traversal ) in binary trees in both recursive and non-recursive methods.

In preorder traversal, we process each node before either of its subtrees. Also, it is the simplest to understand binary tree traversal method. However, even though each node is processed before the subtrees, it still requires some information to be maintained while moving down the tree. Therefore we need to maintain the root information after processing the left subtree so that right subtree can be processed.

Therefore the ADT of choice is STACK, due to its LIFO structure.

Preorder Traversal Steps

• Visit the root.
• Traverse the left subtree in preorder.
• Traverse the right subtree in preorder.

Binary Tree Boiler Plate Code

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.right = None
        self.left = None
# Insert Code below this 


# Don't make changes below this
if __name__ == "__main__":
    root = BinaryTreeNode(1)
    root.left = BinaryTreeNode(2)
    root.right = BinaryTreeNode(3)
    root.left.left = BinaryTreeNode(4)
    root.left.right = BinaryTreeNode(5)
    print("Recursive Traversal")
    PreorderRecursive(root)
    print("\nNon Recursive Traversal")
    PreorderNonRec(root)

Recursive Preorder Traversal

The recursive approach is easy to understand and pretty much straight forward.

def PreorderRecursive(root:BinaryTreeNode)->None:
    if(root == None): 
        return
    print(root.data, end=" ")
    PreorderRecursive(root.left)
    PreorderRecursive(root.right)

Time Complexity – O(n), Space Complexity – O(n)

Non-Recursive Preorder Traversal

In the non-recursive version, we require a STACK ADT as we need to remember the current node so that after processing the left sub-tree we can proceed to right subtree.

To Stimulate the same,

• Process the current node.
• Before going to the left node, store the current node in the stack.
• After processing left subtree, pop an element from the stack.
• Go to its right subtree.
• Continue until the stack is non-empty.

def PreorderNonRec(root:BinaryTreeNode):
    stack = []
    while(1):
        while(root):
            # Process Current Node
            print(root.data, end=" ")
            # push the root into stack
            stack.append(root)
            # go left
            root = root.left
        
        if(len(stack) == 0):
            break
        root = stack.pop()
        # Go to right
        root = root.right

Time Complexity – O(n), Space Complexity – O(n)

Full Code

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.right = None
        self.left = None

def PreorderRecursive(root:BinaryTreeNode)->None:
    if(root == None): 
        return
    print(root.data, end=" ")
    PreorderRecursive(root.left)
    PreorderRecursive(root.right)


def PreorderNonRec(root:BinaryTreeNode):
    stack = []
    while(1):
        while(root):
            # Process Current Node
            print(root.data, end=" ")
            # push the root into stack
            stack.append(root)
            # go left
            root = root.left
        
        if(len(stack) == 0):
            break
        root = stack.pop()
        # Go to right
        root = root.right

if __name__ == "__main__":
    root = BinaryTreeNode(1)
    root.left = BinaryTreeNode(2)
    root.right = BinaryTreeNode(3)
    root.left.left = BinaryTreeNode(4)
    root.left.right = BinaryTreeNode(5)

    print("Recursive Traversal")
    PreorderRecursive(root)
    print("\nNon Recursive Traversal")
    PreorderNonRec(root)

Check our other awesome tutorials below:

• Binary Tree Data Structure in Python
• Introduction to Python Programming

That’s it for this folks, feel free to comment in case of any trouble. I’ll be happy to help. 🙂