Binary tree preorder traversal

Tree traversal is a very important concept when we are working with binary trees, and one of the essential traversal methods is the “preorder traversal.” 

So, when we traverse a binary tree, there are different ways in which we can print or traverse all the nodes of the binary tree by following some traverse algorithm. That traverse algorithm can be a postorder, inorder or preorder traverse approach.

In this blog, we will read about Binary tree preorder traversal and how it works. 

Let’s start reading the blog,

What is Binary tree preorder traversal?

Binary tree preorder traversal approach using depth-first traversal algorithm to visit all the nodes one by one in a binary tree. And this traversal follows a specific order for visiting all the nodes in the binary tree.

So, that approach is:

1. First, we will visit the current (root) node.
2. Then, we will recursively traverse all the nodes of the left subtree of the binary tree.
3. Finally, we will recursively traverse the right subtree in preorder.

In a binary tree for every subtree, we have to follow the same approach till we traverse all the leaf nodes.

How does preorder binary tree traversal work?

To find out its Preorder traversal, we will follow the above approach. That is, we will start by vising the root node of the binary tree. Then, we will move to the left child node of the binary tree and then visits the right child node.

So, In the above figure,

1. We will first take the root Node 1, and the root node has two subtrees.
   (1)
2. Next, we will traverse the left subtree and the next subtree has root Node 2, so the next value will be 2.
   (1->2)
3. Root Node 2 has two child nodes, so first we will take left child Node 4, and then take right Node 5 which is a root Node also.
   (1->2->4->5)
4. Node 5 has only the first child that is left child. So, we will take that Node whose value is 8.
   (1->2->4->5->8).
5. We have covered the left subtree, now we will move to the right subtree.
6. The right subtree has a root Node 3. So, we will take that Node first.
   (1->2->4->5->8->3)
7. Then, we will move to the left child node of the root Node 3. So, the next Node we take will be Node 6 which is the left child node.
   (1->2->4->5->8->3->6)
8. As root Node 3 has only one child, we will move to the right subtree. That subtree has a root Node 7. So, we will take that node next.
   (1->2->4->5->8->3->6->7)
9. Now we will take the left child that is Node 9 and finally Node 10.
   (1->2->4->5->8->3->6->7->9->10)

So, in this way, we will traverse the node of the binary tree in a preorder manner.

How to implement the preorder traversal algorithm?

We can implement the preorder traversal algorithm by using either iterative or recursive approaches.

Code:

#include <iostream>
using namespace std;

// Definition for a binary tree node
struct Node {
    int data;
    Node* left;
    Node* right;

    // Constructor
    Node(int val) {
        data = val;
        left = NULL; 
        right = NULL; 
    }
};

// Recursive Preorder Traversal
void preorderTraversal(Node* root) { 
    if (root == NULL) // Replace nullptr with NULL
        return;

    // Visit the current (root) node
    cout << root->data << " ";

    // Recursively traverse the left subtree in preorder
    preorderTraversal(root->left);

    // Recursively traverse the right subtree in preorder
    preorderTraversal(root->right);
}

int main() {
    // Sample binary tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
   

    cout << "Preorder Traversal: ";
    preorderTraversal(root);
    cout << endl;

    return 0;
}

Here, In the above code, we are using a recursive approach:

So, In the above code,

1. We will first define the “TreeNode” structure to represent nodes in the binary tree, where each node has an integer value and pointers to its left and right children.
2. Next, we will make a “preorderTraversal” function which is a recursive function that performs the preorder traversal for every node in the binary tree.
3. So, when we call the “preorderTraversal” function with the root node “root” as a parameter, it will print the nodes in preorder traversal order one by one.
   So, the order of node visits in the preorder traversal is the root, left subtree, and then right subtree.

Output: