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

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more