Binary search tree is quite an intriguing and useful concept for the coders!
From top and bottom view of a binary tree, to binary tree heap to pre and post order traversal to diameter of a binary tree, the concepts uncover some crucial sub concepts.
If you want your coding interview preparation at the top of charts, you can’t take the risk of leaving this topic behind.
One such binary tree concept that we will be discussing in this guide is preorder traversal of a binary tree.
Preorder traversal is recognised as a depth first search traversal strategy where we traverse the root or the current node to get the left and the right subtree!
This process will repeat recursively until we have traversed all the nodes of a given tree.
Though, the concept holds much more in it!
Be on the subject and arm yourself with all the crucial details regarding the preorder traversal of a binary tree.
Let’s get started!
Binary search tree - A Snapshot
Binary search tree in a defined data structure is a tree that allows for the maintenance of the sorted list in a given number.
The tree is called the binary tree as each of its nodes will have the maximum of at least two children. It is also called the search tree as it would be useful to search the presence of required numbers of O[log n] times.
Preorder traversal of a binary tree
Traversing any tree would mean to visit and output its values of all the nodes in the particular tree nodes. The importance of a tree traversal is to get multiple ways in carrying out all types of traversal operations.
A preorder traversal in the binary tree is touted as the type of a tree order traversal who aims at visiting the first tree node which will be then followed by your left subtree to reach till the right subtree.
This is known as preorder traversal as the root nodes in this case will always be visited before their child nodes. Sometimes, we can also call the pre-order traversal as the depth-first search traversal.
Applications of the preorder traversal in a binary search tree
Reorder traversal is widely known as a technique that is useful to traverse your graphs or trees. Some of the wonderful applications of the preorder traversal may includes;
Generating all types of lists of the files in the given directory of tree
Parsing of the XML documents
Construction of syntax trees for the compilers
Calculation of all types of mathematical expressions for the given prefix notation
Conversion of the infix notation to that of the prefix notation
Working of the preorder traversal
In the case of preorder traversal in a binary tree, firstly the root node gets visited. After that the left subtree is visited and the right subtree is visited in any case.
The process in this case will be represented in the form:
Root ➡ left ➡ right
Firstly, the root node in any case would be traversed as first in a preorder traversal. Though, the last item of a preorder traversal would stay as it is. This preorder traversal will be useful to get a prefix expression of any given tree.
The steps that needs to be taken in this case are as follows:
Firstly, you need to visit the root node
After that visit the left subtree
Then visit the right subtree
The pre order technique would be followed with the root node policy. The name of the preorder would itself convey that the root node is the one that will be first traversed.
Let’s understand with an example:
Root
40
↙ ↘
30 50
↙ ↘ ↙ ↘
25 35 45 60
↙ ↘ ↙ ↘
15 28 55 70
Now, we are going to traverse all the nodes of the above tree by taking the help of a preorder traversal of a binary tree.
First start with a root node that is 40. Then print it and recursively traverse the required left subtree.
No move towards your left subtree. For the left subtree, the root node would be 30. Print it and then move towards your left subtree which is 30.
In the case of the left subtree that is 30, there would be the element of 25 that you need to print. Traverse this tree in the required order.
In the case of the left subtree that is 25, there will be the element 15 and it has no subtree. So, you need to print 15 by moving towards the subtree 25.
In the case of the right subtree which is 25, there will be 28 which have no subtree. So, you need to print 28 and then move to the right subtree which is 30.
In the right subtree which is 30, there would be 35 that have no subtree. Traverse the right subtree that is 40.
In the case of the right subtree which is 40, there will be 50. You can print 50 and traverse it to the left subtree that is 50.
In the case of the left subtree which is 50, there will be 45 which don’t have a child. Print 45 and traverse it with the right subtree.
In the right subtree 50, there will be 60. Print it and restructure the left subtree. In the case of the left subtree 60, there will be 50 that are having no child. Print 55 to move it towards 60.
In the case of the right subtree 60, there will be 70 who don’t have a child. Print 70 to stop the process.
After the completion of your preorder traversal you will get the final output that is;
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Wrapping Up
From binary tree types to binary tree heap to diameter of binary tree, the concept holds some crucial sub concepts that can be asked from the aspirants.
Learn preorder traversal of binary trees with the help of this blog post and ace in this topic!