What is Preorder Traversal and implementation

In this blog, we would discuss What is Preorder Traversal and its implementation. Preorder traversal is a type of tree traversal in which the root node is visited first, followed by the left subtree, and then the right subtree. This is in contrast to postorder and inorder traversals, which visit the left and right subtrees before the root node.

 

 

Preorder traversal is a useful technique for reading a binary tree since it allows us to process the root node first and then recurse down the left and right subtrees. This is especially helpful when we want to print out the contents of a tree, as we can simply print out the root node first and then recurse down the left and right subtrees.

 

 

 

 

What is Preorder traversal? 

 

Preorder traversal is a type of tree traversal that visits the nodes of a tree in a specific order. The order in which the nodes are visited is: root, left, right. Preorder traversal is a very useful traversal for tasks such as creating a copy of a tree, or calculating the size of a tree. Preorder traversal can be implemented using recursion or using an iterative approach.

 

 

Recursive preorder traversal: The recursive preorder traversal algorithm is very simple. It consists of a single function that takes as input the root node of a tree. The function then visits the root node, followed by the left subtree, and then the right subtree.

 

 

Iterative preorder traversal: The iterative preorder traversal algorithm is a little more complicated than the recursive algorithm. It uses a stack to keep track of the nodes that need to be visited. The algorithm starts by pushing the root node onto the stack. Then, while the stack is not empty, the algorithm pops a node off the stack and visits it.

 

 

If the node has a left child, the algorithm pushes the left child onto the stack. If the node has the right child, the algorithm pushes the right child onto the stack. Preorder traversal is a very important tree traversal algorithm. It has many uses and can be implemented using either a recursive or iterative approach.

 

 

Preorder traversal is a very simple algorithm, but it has a major advantage over other algorithms: it is guaranteed to visit the root node before any of the child nodes. This means that if the root node contains information that is needed in order to process the child nodes, that information will be available.

 

 

There are a few disadvantages to preorder traversal as well. First, it is not the most efficient algorithm for large trees. Second, it is not the most intuitive algorithm for humans to understand. However, for small trees or for situations in which the root node contains important information, preorder traversal is a good choice.

 

 

 

 

Implementation of preorder traversal

 

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def printPreorder(root):
  
    if root:
        print(root.val),
        printPreorder(root.left)
        printPreorder(root.right)
  

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Preorder traversal of binary tree is")
printPreorder(root)

 

Output

 

 

 

 

Applications of preorder traversal

 

• Preorder traversals are commonly used when creating or manipulating trees. For example, when creating a binary search tree, a preorder traversal can be used to insert nodes into the tree in the correct order. Additionally, preorder traversals can be used to evaluate mathematical expressions stored in trees.

 

• Preorder traversals can also be used to generate a list of all the nodes in a tree. This can be useful, for example, when you want to know how many nodes are in a tree, or when you want to find the maximum or minimum value in a tree.

 

• Preorder traversal can be used to create a copy of a tree. It can also be used to calculate the size of a tree or the height of a tree.

 

• Preorder traversal can also be used to find the shortest path between two nodes in a tree.

 

• Preorder traversal can be used to evaluate an expression tree.

 

• Preorder traversal can also be used to construct a Huffman tree.

 

 

 

Also, read about level order traversal.