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..!
Leave a Reply