Top 10 Programming Languages to Learn in 2019

ProgrammingPythonPython Data Structures

Preorder Traversal of Binary Tree in Python

Preorder Traversal 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:

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

Related posts
ProgrammingPythonPython Basic Tutorial

Mastering Print Formatting in Python: A Comprehensive Guide

ProgrammingPython

Global Variables in Python: Understanding Usage and Best Practices

ProgrammingPythonPython Basic Tutorial

Secure Your Documents: Encrypting PDF Files Using Python

ProgrammingPython

Creating and Modifying PDF Files in Python: A Comprehensive Guide with Code Examples

1 Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: