Top 10 Programming Languages to Learn in 2019

# 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.

Page Contents

## 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. 🙂

## 1 Comment

• 