Pre-Order Tree Traversal in Python
Pre-order tree traversal is basically traversing the Root, Left, and Right node of each sub-tree. We can understand it better by using below algorithm:
- Visit the root node.
- Traverse the left subtree by recursively calling the preorder traversal function.
- Traverse the right subtree by recursively calling the preorder traversal function.
Example:
The given code defines a binary tree and demonstrates the preorder traversal technique. The `Node` class defines each node of the tree with attributes for its data, left child, and right child. The `printPreOrder` function carries out a recursive preorder traversal, which involves: first visiting and printing the current node’s data, then traversing the left subtree, followed by traversing the right subtree. In the driver code, a sample binary tree is constructed with nodes having values ranging from 10 to 300. The function `printPreOrder` is then invoked on the root of this tree, printing the nodes in the order dictated by the preorder traversal.
Python3
class Node: def __init__(self, v): self.data = v self.left = None self.right = None# Preorder Traversaldef printPreOrder(node): if node is None: return # Visit Node print(node.data, end = " ") # Traverse left subtree printPreOrder(node.left) # Traverse right subtree printPreOrder(node.right)# Driver codeif __name__ == "__main__": # Build the tree root = Node(95) root.left = Node(15) root.right = Node(220) root.left.left = Node(10) root.left.right = Node(30) root.right.left = Node(160) root.right.right = Node(285) # Function call print("Preorder Traversal: ", end = "") printPreOrder(root) |
Preorder Traversal: 95 15 10 30 220 160 285
Tree Traversal Techniques in Python
A tree is a non-linear data structure or we can say that it is a type of hierarchical structure. It is like an inverted tree where roots are present at the top and leaf or child nodes are present at the bottom of the tree. The root node and its child nodes are connected through the edges like the branches in the tree. In this article, we will learn different ways of traversing a tree in Python.
Prerequisites for Tree Traversal in Python
- Basics of Classes and Objectes in Python.
- Basics of Tree Data structure.
Contact Us