Preorder Traversal of Binary Tree

Introduction to Preorder Traversal of Binary Tree

Preorder traversal of binary tree is a traversal method, where the root node is visited first, then left subtree and then the right sub tree. Unlike array and linked lists, linear data structures, we have several ways of traversing binary trees due to their hierarchical nature. These tree traversal algorithms are divided into two types, i.e., Depth First Algorithms and Breadth First Algorithms. In-Depth First Algorithm, trees are traversed downwards. Preorder, Inorder, Postorder are actually depth-first traversal algorithms. Preorder traversal will make a copy of the tree and is used to get the prefix of an expression.

How Preorder Traversal of Binary Tree Works?

• In preorder traversal, the root node is visited first, then left subtree and then right subtree.
• Unlike other data structures, such as Array, Queue, Stack, etc., which have only one way of traversal, trees have 3 ways of traversal, i.e., Inorder, Preorder, and Postorder traversals.

Let us consider an example of a Binary tree for Preorder traversing.

• We shall perform Depth First Traversal on the above Binary tree; Depth First consists of Preorder, Inorder and Postorder; we shall see Preorder traversing here.
• Preorder( Root, Left Subtree, Right Subtree ): A B D E C.
• Steps followed to get Preorder is simple, visit the root node first, i.e. A, then traverse to the left node of the root, i.e. B, as node B has child nodes, traverse to the left node of the subtree, i.e., D.
• As there are no other subtrees to node D, move to the right node, i.e., E.
• As there are no other subtrees to node E, move to the top and check if there is any other right node to the root node, i.e. C.
• And hence preorder traversal will move as [A, B, D, E, C].

Algorithm of Preorder Traversal

Given below is the algorithm of Preorder Traversal:

• Step 1: Visit the root node.
• Step 2: Traverse the left sub tree, i.e., traverse recursively.
• Step 3: Traverse the right sub tree, i.e., traverse recursively.
• Step 4: Repeat steps 2 and 3 until all the nodes are visited.

Binary tree preorder traversal can be implemented recursively or by using stack data structure through any programming language.

Let us see one more binary tree for implementing preorder traversal.

Preorder Traversal: A, B, C, D, F, E

• The first element printed is A, traversing the left sub tree, and the root node of the left is B.
• There are no sub trees for root node B; hence we move to the right sub tree, i.e., C.
• Left sub tree for root node C has only left node, i.e., D, it has sub tree with another left node, i.e. F.
• As there is no right sub tree, move to the top where you can find any right sub tree. Here it is E.
• Hence, a tree is printed as A, B, C, D, F, E.

Advantages and Disadvantages of Preorder Traversal of Binary Tree

Given below are the advantages and disadvantages mentioned:

Advantages:

• Preorder traversal is used to create a copy of the binary tree.
• It is used to get the prefix of an expression.
• Binary tree traversals give quick searching, insertion, and deletion in cases where the tree is balanced.
• In Preorder traversal, the root node value is printed before visiting the left subtree and right subtree.
• It is also part of the Depth-First Algorithm, and order is root node > left sub tree > right sub tree; hence it is also known as the NLR algorithm.
• Preorder Traversal, part of the Depth first algorithm, will use less memory space as compared to the Breadth first algorithm.

Disadvantages:

• Preorder traversal works well while traversing trees. However, as it is a depth first algorithm, searching graphs can get you struck in an infinite loop as depth first algorithms travel around in a cyclic manner for graphs forever.
• There is no possibility to get the shortest path while traversing.
• In Preorder traversal, on duplicating nodes and values can make a complete duplicate of the tree.

Conclusion

With this, we shall conclude the topic ‘Preorder Traversal of Binary tree’. We have seen what Preorder traversal is and its algorithm. Also implemented few sample examples to illustrate the preorder traversal algorithm practically. A binary tree can be traversed in two types, Breadth first traversal and Depth first traversal. Depth-first traversal includes preorder, inorder and postorder traversals. Out of which, we have seen preorder traversal here. We have also listed out the Advantages and Disadvantages of Preorder traversal in the Binary tree.

Recommended Articles

This is a guide to Preorder Traversal of Binary Tree. Here we discuss the introduction, working, algorithm, advantages and disadvantages, respectively. You may also have a look at the following articles to learn more –

1. B Tree in Data Structure
2. B+ Tree in Data Structure
3. Decision Tree in Data Mining
4. AVL Tree in Data Structure