Tree Traversals

There are three common types of binary tree traversals: in-order, pre-order, and post-order. These traversals define the order in which the nodes of the binary tree are visited.

// Definition of a binary tree node 
struct TreeNode {
int data; 
struct TreeNode* left; 
struct TreeNode* right; 
};

In-Order Traversal:

In in-order traversal, we visit the left subtree, then the current node, and finally the right subtree.

Algorithm:
  • Traverse the left subtree in-order.
  • Visit the current node.
  • Traverse the right subtree in-order.

Pseudocode  In-order Traversal 
procedure inOrderTraversal(node): 
    if node is not null: 
    // Recur on left subtree 
        inOrderTraversal(node.left) 
    // Process current node 
        print(node.data) 
    // Recur on right subtree 
        inOrderTraversal(node.right)

Pre-Order Traversal:

In pre-order traversal, we visit the current node, then the left subtree, and finally the right subtree.

Algorithm:
  • Visit the current node.
  • Traverse the left subtree pre-order.
  • Traverse the right subtree pre-order.
Pseudocode  Pre-order Traversal 
procedure preOrderTraversal(node):
 if node is not null: 
    // Process current node 
        print(node.data) 
    // Recur on left subtree 
        preOrderTraversal(node.left) 
    // Recur on right subtree 
        preOrderTraversal(node.right)

Post-Order Traversal:

In post-order traversal, we visit the left subtree, then the right subtree, and finally the current node.

Algorithm:
  • Traverse the left subtree post-order.
  • Traverse the right subtree post-order.
  • Visit the current node.
Pseudocode-Post-order Traversal 
procedure postOrderTraversal(node): 
if node is not null:
 // Recur on left subtree 
    postOrderTraversal(node.left) 
// Recur on right subtree 
    postOrderTraversal(node.right) 
// Process current node 
    print(node.data)

Note:In each traversal, every node is visited exactly once, leading to a linear time complexity relative to the number of nodes in the tree. The O(N) time complexity is a common characteristic for tree traversals.

Example:


In-Order Traversal:
In in-order traversal, we visit the left subtree, then the current node, and finally the right subtree.
D B E A F C G

Pre-Order Traversal:
In pre-order traversal, we visit the current node, then the left subtree, and finally the right subtree.
A B D E C F G

Post-Order Traversal:
In post-order traversal, we visit the left subtree, then the right subtree, and finally the current node.
D E B F G C A

Example:Write the inorder, preorder and postorder traversal of the following Tree ( University question)
In-Order Traversal:
In in-order traversal, we visit the left subtree, then the current node, and finally the right subtree.
A B C D E F G H I

Pre-Order Traversal:
In pre-order traversal, we visit the current node, then the left subtree, and finally the right subtree.
 F B A D C E G I H

Post-Order Traversal:
In post-order traversal, we visit the left subtree, then the right subtree, and finally the current node.
A C E D B H I G F

C Implementation- Binary Tree Traversals
/*******************************************************/
#include <stdio.h>
#include <stdlib.h>

// Definition of a binary tree node
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// Function to create a new node with a given data value
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// In-Order Traversal
void inOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

// Pre-Order Traversal
void preOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}

// Post-Order Traversal
void postOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        postOrderTraversal(root->left);
        postOrderTraversal(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    // Creating a binary tree
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // Performing in-order traversal
    printf("In-Order Traversal: ");
    inOrderTraversal(root);
    printf("\n");

    // Performing pre-order traversal
    printf("Pre-Order Traversal: ");
    preOrderTraversal(root);
    printf("\n");

    // Performing post-order traversal
    printf("Post-Order Traversal: ");
    postOrderTraversal(root);
    printf("\n");

    // Remember to free allocated memory
    // (This is a simple example; in practice, memory management needs to be handled appropriately)

    return 0;
}
Output:
In-Order Traversal: 4 2 5 1 3 Pre-Order Traversal: 1 2 4 5 3 Post-Order Traversal: 4 5 2 3 1

Level order traversal, also known as breadth-first traversal, visits the nodes of a binary tree level by level, starting from the root and moving down the tree. The algorithm uses a queue to keep track of the nodes at each level.

Level Order Traversal Algorithm:
Algorithm

Enqueue the root node into a queue.
While the queue is not empty:
    Dequeue a node from the front of the queue and process it.
    Enqueue its left child (if it exists).
    Enqueue its right child (if it exists).

Example:
Level order traversal; 1 2 3 4 5

C Program Implementation - Level Order Traversal
/*******************************************************************************/ 
#include <stdio.h>
#include <stdlib.h>

// Definition of a binary tree node
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// Node for a queue used in level order traversal
struct QueueNode {
    struct TreeNode* data;
    struct QueueNode* next;
};

// Structure for the queue
struct Queue {
    struct QueueNode *front, *rear;
};

// Function to create a new node with a given data value
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function to create a new node for the queue
struct QueueNode* createQueueNode(struct TreeNode* data) {
    struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to initialize a queue
struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}

// Function to enqueue a node into the queue
void enqueue(struct Queue* q, struct TreeNode* data) {
    struct QueueNode* newNode = createQueueNode(data);
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

// Function to dequeue a node from the queue
struct TreeNode* dequeue(struct Queue* q) {
    if (q->front == NULL)
        return NULL;
    struct QueueNode* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL)
        q->rear = NULL;
    struct TreeNode* node = temp->data;
    free(temp);
    return node;
}

// Function for level order traversal
void levelOrderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;

    // Create a queue for level order traversal
    struct Queue* q = createQueue();

    // Enqueue the root node
    enqueue(q, root);

    // Process nodes level by level
    while (q->front != NULL) {
        // Dequeue a node and process it
        struct TreeNode* currentNode = dequeue(q);
        printf("%d ", currentNode->data);

        // Enqueue its left child (if it exists)
        if (currentNode->left != NULL)
            enqueue(q, currentNode->left);

        // Enqueue its right child (if it exists)
        if (currentNode->right != NULL)
            enqueue(q, currentNode->right);
    }

    // Free the queue
    free(q);
}

int main() {
    // Creating a binary tree
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // Performing level order traversal
    printf("Level Order Traversal: ");
    levelOrderTraversal(root);
    printf("\n");

    // Remember to free allocated memory
    // (This is a simple example; in practice, memory management needs to be handled appropriately)

    return 0;
}

Output:
Level Order Traversal: 1 2 3 4 5

Constructing the  Tree from given Inorder and Preorder Traversals

Give the preorder/postorder and the inorder traversal , we can construct a binary tree

  1. Algorithm

  2. Pick the Root:

    • The first element in the pre-order traversal is the root of the tree.

  3. Locate the Root in In-Order Traversal:

    • Find the index of the root element in the in-order traversal. The elements before this index represent the left subtree, and elements after represent the right subtree.

  4. Recursively Build Left and Right Subtrees:

    • Recursively construct the left subtree using the elements from the left side of the root in the in-order traversal.
    • Recursively construct the right subtree using the elements from the right side of the root in the in-order traversal.
Let us consider the below traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

In a Preorder sequence, the leftmost element is the root of the tree. So we know ‘A’ is the root for given sequences. By searching ‘A’ in the Inorder sequence, we can find out all elements on the left side of ‘A’ is in the left subtree and elements on right in the right subtree. So we know the below structure now.
Now we can do the above steps recursively.From the preorder we know that 'B' is the root of the left subtree and 'C' is the root of the right subtree.From the inorder we can also identify the left and right subtree.So the final tree become.



C Program- Implementation

/* program to construct tree using inorder and preorder traversals */
#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    char data;
    struct node* left;
    struct node* right;
};
 
/* Prototypes for utility functions */
int search(char arr[], int strt, int end, char value);
struct node* newNode(char data);
 
/* Recursive function to construct binary of size len from
   Inorder traversal in[] and Preorder traversal pre[].  Initial values
   of inStrt and inEnd should be 0 and len -1.  The function doesn't
   do any error checking for cases where inorder and preorder
   do not form a tree */
struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)
{
    static int preIndex = 0;
 
    if (inStrt > inEnd)
        return NULL;
 
    /* Pick current node from Preorder traversal using preIndex
    and increment preIndex */
    struct node* tNode = newNode(pre[preIndex++]);
 
    /* If this node has no children then return */
    if (inStrt == inEnd)
        return tNode;
 
    /* Else find the index of this node in Inorder traversal */
    int inIndex = search(in, inStrt, inEnd, tNode->data);
 
    /* Using index in Inorder traversal, construct left and
     right subtress */
    tNode->left = buildTree(in, pre, inStrt, inIndex - 1);
    tNode->right = buildTree(in, pre, inIndex + 1, inEnd);
 
    return tNode;
}
 
/* UTILITY FUNCTIONS */
/* Function to find index of value in arr[start...end]
   The function assumes that value is present in in[] */
int search(char arr[], int strt, int end, char value)
{
    int i;
    for (i = strt; i <= end; i++) {
        if (arr[i] == value)
            return i;
    }
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(char data)
{
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
/* This function is here just to test buildTree() */
void printInorder(struct node* node)
{
    if (node == NULL)
        return;
 
    /* first recur on left child */
    printInorder(node->left);
 
    /* then print the data of node */
    printf("%c ", node->data);
 
    /* now recur on right child */
    printInorder(node->right);
}
 
/* Driver program to test above functions */
int main()
{
    char in[] = { 'D', 'B', 'E', 'A', 'F', 'C' };
    char pre[] = { 'A', 'B', 'D', 'E', 'C', 'F' };
    int len = sizeof(in) / sizeof(in[0]);
    struct node* root = buildTree(in, pre, 0, len - 1);
 
    /* Let us test the built tree by printing Inorder traversal */
    printf("Inorder traversal of the constructed tree is \n");
    printInorder(root);
    return 0;
}


Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Stack

Image
A stack is a fundamental data structure in computer science and programming that follows the Last-In, First-Out (LIFO) principle . It is named "stack" because it resembles a stack of items, like a stack of plates or books, where you can only add or remove items from the top. Stacks are used for various purposes in programming and are essential in many algorithms and applications. Let's delve into the details of stacks: Key Operations:  A stack typically supports two primary operations: Push: This operation adds an element to the top of the stack. It is analogous to placing an item on top of the stack. Pop: This operation removes and returns the top element of the stack. It is like taking the top item off the stack. Additionally, stacks often provide the following operations: Peek (or Top): This operation retrieves the top element without removing it. It allows you to examine the top item without modifying the stack. IsEmpty: This operation checks if the stack is empty.
Read more

Quick Sort

Quick sort is a popular sorting algorithm that uses a divide-and-conquer strategy to efficiently sort an array or list. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Here's a detailed algorithm for the Quick Sort algorithm: Algorithm: Quick Sort 1.Choose a pivot element from the array. This can be done in various ways, such as selecting the first element, the last element, or a random element. The choice of the pivot can affect the algorithm's performance. 2,Partition the array into two sub-arrays:     Elements less than the pivot (left sub-array).     Elements greater than the pivot (right sub-array). 3.Recursively apply the Quick Sort algorithm to the left and right sub-arrays. 4.Combine the sorted left sub-array, pivot, and sorted right sub-array to obtain the final sorted ar
Read more