What is pre-order traversal on the binary tree?

Share

In linear data structures like Array, Linked List, Queues, Stacks, etc have only one logical way to traverse them. Unlike them, tree can be traversed in different ways.

pre-order, in-order, and post-order are some generally used techniques of tree traverse.

Pre-order Traversal

Algorithm:

  1. Visit the root
  2. Traverse the left sub-tree
  3. Traverse the right sub-tree

Let us consider the following tree given for pre-order traversal.

Let’s understand the pre-order traversal with c-program codes.

Firstly, we create a structure for a node. In the tree, each node has a structure like the following:

NULL| Node Data| NULL

To implement the structure we define a structure in C-program:

struct node {
	int data;
	struct node* left;
	struct node* right;
};

Then we assign a value to each node from the given tree. To do so, we create a helper function that creates a node with a given value and assigns NULL to the left and right nodes.

 struct node* createNewNode(int data)
{
	struct node* node = (struct node*)malloc(sizeof(struct node));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return (node);
 }

Understanding the above function:

It takes a value to be inserted into the node as an argument. Then, using DMA, it allocates memory for a new node after that the given value is assigned to the new node following by assigning NULL to left and right nodes.

Assigning values to each node:

struct node* root = createNewNode(11); //root
	root->left = createNewNode(12);
	root->right = createNewNode(13);
	root->left->left = createNewNode(14);
	root->left->right = createNewNode(15);
	root->right->left = createNewNode(16);
	root->right->right = createNewNode(17);

Understanding the above code:

At first, we created a pointer variable for the root node and assign the root value to it using createNewNode function.

Pre-order traversal

Now, the main deal comes in role i.e. pre-order traversal. For traversing the tree, we use a recursive function that prints the node value if not null and then looks for the node value of its left subtree. after finishing the traversing of the left sub-tree it looks after the right sub-tree in the same manner for every node.

The above figure shows, how the traversing process is going on. you can see, each left node is traversed first and then goes to the right node ( or sub-tree). C-program function for pre-order traverse and print the value is as follow:

void preorderTraverse(struct node* node)
{
	if (node == NULL){
           return;
        }

	/* first print data of node */
	printf("%d ", node->data);

	/* then recur on left subtree */
	printPreorder(node->left);

	/* now recur on right subtree */
	printPreorder(node->right);
}

Understanding the above code:

It accepts a binary tree and checks if the tree is not null. then it prints the value in node and recurs on the left subtree and the process recurs until the last node is found to be NULL. once it is found, the flow raches to the line where it recurs on the right sub-tree.

complete C-program and online compiler: https://onlinegdb.com/SwjASy-I6

Blogs for CSIT students

Share
Sudeep Mishra

Sudeep Mishra

Healing

Leave a Reply

Your email address will not be published.

%d bloggers like this: