Binary Tree Preorder Traversal Explained With Simple Example

A tree is a data structure similar to Linked list in which each node points to multiple nodes instead of simply pointing to the next node. A tree is called Binary tree if each node in a tree has maximum of two nodes.
An empty tree is also a Binary tree. We can call the two children of each node as Left and Right child of a node. The node of the tree which has no parent is called the Root of the tree. Perhaps Binary tree is the most used tree data structure in the programming world. Before going ahead have a look into Binary Tree basics and Binary Tree implementation.

Binary Tree Traversal

Binary Tree has multiple ways in which nodes can be accessed which is quite different that other data structures such as Stacks, Queues etc which follows one certain method such as LIFO, FIFO etc for accessing it’s elements.
There are multiple ways to traverse a Binary Tree.

• Inorder Traversal — In Inorder Traversal root node is visited in between it’s left and right child.
• Preorder Traversal — In Preorder Traversal root node is visited before it’s left and right child.
• Postorder Traversal — In Postorder Traversal root node is visited after it’s left and right child.
• Level order Traversal — In Level order Traversal, all the nodes present in same level is visited first and then their children will be visited.

In this article, we are going to talk about the Preorder Traversal.

Preorder Traversal

In Preorder Traversal root node is visited in before it’s left and right child. Algorithm for Preorder traversal can be defined as mentioned below.

Algorithm

• Visit the root.
• Visit the left subtree of the root in Preorder Traversal.
• Visit the right subtree of the root in Preorder Traversal.

Let’s look into an example to understand it better.

For the Binary tree mentioned in above image, Preorder traversal would be 5, 3, 2, 1, 4, 7, 6, 9, 8, 10

Important points

• In Preorder traversal first entry is always the root node present in the the tree.
• In Preorder traversal last entry is always the rightmost node present in the the tree.
• Looking into Preorder traversal, leftmost node can’t be identified.

Let’s have a look on basic class definition for Binary Tree.

class BinaryTree
{
    public:
        int m_data;
        BinaryTree* m_left;
        BinaryTree* m_right;
        BinaryTree (int data);
        BinaryTree (int data, BinaryTree* left, BinaryTree* right);
        ~BinaryTree ();
};

void print_binary_tree (BinaryTree* root)
{
    cout << " " << root -> m_data;
    if (root -> m_left)
        print_binary_tree (root -> m_left);
    if (root -> m_right)
        print_binary_tree (root -> m_right);
}

void print_tree (BinaryTree* root)
{
    cout << "Binary tree contents: ";
    print_binary_tree (root);
    cout << endl;
}

Let’s look into the sample code for Preorder Traversal.

/* order of accessing nodes in preorder traversal is 
 * Parent - Left - Right
 */
void preorder_traversal (BinaryTree* root)
{
    if (!root)
        return;
    cout << " " << root -> m_data;
    if (root -> m_left)
        preorder_traversal (root -> m_left);
    if (root -> m_right)
        preorder_traversal (root -> m_right);
}

Few of the functions used below are explained in Binary Tree Implementation. Refer those before going ahead.
Let’s define a main function to use above functions.

int main ()
{
    BinaryTree* node1 = new BinaryTree (1);
    BinaryTree* node2 = new BinaryTree (2);
    BinaryTree* node3 = new BinaryTree (3);
    BinaryTree* node4 = new BinaryTree (4);
    BinaryTree* node5 = new BinaryTree (5);
    BinaryTree* node6 = new BinaryTree (6);
    BinaryTree* node7 = new BinaryTree (7);
    BinaryTree* node8 = new BinaryTree (8);
    BinaryTree* node9 = new BinaryTree (9);
    BinaryTree* node10 = new BinaryTree (10);

    /* Set node5 as root node */
    BinaryTree* root = node5;
    node5 -> m_left = node3;
    node3 -> m_left = node2;
    node3 -> m_right = node4;
    node2 -> m_left = node1;

    node5 -> m_right = node7;
    node7 -> m_left = node6;
    node7 -> m_right = node9;
    node9 -> m_right  = node10;
    node9 -> m_left = node8;
    print_tree (root);
    cout << " Preorder Traversal: ";
    preorder_traversal (root);
    cout << endl;
    delete_all_nodes (root);
}

Let’s analyze the output of this main function.

Binary tree contents:  5 3 2 1 4 7 6 9 8 10
Preorder Traversal:  5 3 2 1 4 7 6 9 8 10

Preorder Traversal Applications

• Preorder traversal mainly used in duplicating a Binary Tree.
• Preorder traversal can also be used with expression trees to get the prefix expressions.