Binary Tree Traversals and Building Binary Tree given the Traversal data

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 

 inOrderTraversal(node)
    if node is not null: 
        inOrderTraversal(node.left)   // Recur on left subtree 
        print(node.data)                      // Process current node 
        inOrderTraversal(node.right)  // Recur on right subtree 

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 

preOrderTraversal(node)
 if node is not null: 
        print(node.data)                         // Process current node 
        preOrderTraversal(node.left)     // Recur on left subtree 
        preOrderTraversal(node.right)   // Recur on right subtree 

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.
Post-order Traversal 

postOrderTraversal(node)
if node is not null:
    postOrderTraversal(node.left)   // Recur on left subtree 
    postOrderTraversal(node.right)  // Recur on right subtree 
    print(node.data)                         // Process current node 

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;
}

✅ Algorithm: Build a BST from Preorder Traversal

Input: Preorder traversal array.

Output: Root of the reconstructed BST.

Idea

  • In preorder: Root → Left → Right.

  • The first element of preorder is always the root.

  • All elements smaller than root go to the left subtree.

  • All elements greater than root go to the right subtree.

  • Recursively apply this rule.

Example

Preorder = [40, 30, 20, 35, 50, 45, 60]

  1. Root = 40

    • Left subtree = [30, 20, 35] (all < 40)

    • Right subtree = [50, 45, 60] (all > 40)

  2. Left part [30, 20, 35]

    • Root = 30

    • Left subtree = [20], Right subtree = [35]

  3. Right part [50, 45, 60]

    • Root = 50

    • Left subtree = [45], Right subtree = [60]

👉 Final BST:

        40
       /  \
     30    50
    / \    / \
   20 35  45 60
   

   ✅ C Program Example
#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

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

// Function to build BST from preorder
struct Node* buildBST(int preorder[], int start, int end) {
    if (start > end)
        return NULL;

    struct Node* root = newNode(preorder[start]);

    // Find the first element greater than root
    int split = start + 1;
    while (split <= end && preorder[split] < preorder[start])
        split++;

    root->left = buildBST(preorder, start + 1, split - 1);
    root->right = buildBST(preorder, split, end);

    return root;
}

// Inorder traversal (to check correctness)
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    int preorder[] = {40, 30, 20, 35, 50, 45, 60};
    int n = sizeof(preorder) / sizeof(preorder[0]);

    struct Node* root = buildBST(preorder, 0, n - 1);

    printf("Inorder traversal of constructed BST: ");
    inorder(root);
    printf("\n");

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Dr Binu V P

About Me Syllabus and Evaluation Scheme  Model Question Paper and Answers PCCST303 Data Structures and Algorithms Try the following programs in lab to understand the theory better 1.Basic Concepts of Data Structures Stacks and Queues     Data Structures and Data Abstraction     Time and Space Complexity     Asymptotic Analysis and Asymptotic Notations     Best case, Worst case and Average Case Analysis of Algorithms     Frequency Count Method of Algorithm Analysis          Array as a Data Structure     Polynomial Representation using arrays      Polynomial Addition using arrays      Sparse Addition and Transpose     Stacks     Multi Stacks      Queue using array      Circular Queue using array      Double ended Queue using array     Infix to postfix and postfix evaluation     Infix to ...
Read more

Memory Allocation - First Fit

  Memory Allocation Strategy When a program requests memory from the operating system (OS) — say for creating variables, arrays, or objects — the OS must decide where in the memory to place this data. This decision-making is known as a Memory Allocation Strategy . In dynamic memory allocation, main memory (RAM) is managed in chunks called blocks . As programs request and release memory, the memory space gets fragmented into free and occupied blocks. So, an important task for the OS is to find an appropriate free block when a program requests memory. To manage this efficiently, different allocation strategies are used. First Fit Memory Allocation Strategy Definition : In the First Fit strategy, the OS searches from the beginning of memory and allocates the first free block that is large enough to satisfy the request. It doesn't check all blocks. As soon as a large enough block is found, allocation happens. Example : Assume free memory blocks of sizes: 200KB , 500KB ,...
Read more

Performance Analysis - Time and Space Complexity

Image
  📚 Performance Analysis  Performance analysis means studying how efficient an algorithm or data structure is. Mainly, we check two things: Time Complexity — How much time (number of operations) the algorithm takes. Space Complexity — How much memory (space) the algorithm uses. ✅ Goal : To predict how the algorithm will behave as the input size grows without running the code. 📍 1. Time Complexity Measures the amount of time an algorithm takes to complete. It is expressed as a function of the input size n . We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it. ⏳ Why it matters? Because we want algorithms that are fast even for large inputs . Example for Time Complexity: Suppose we have a simple loop: for ( int i = 0 ; i < n; i++) { printf ( "%d " , i); } The loop runs n times . Each printf is a constant-time operation. So, Time Complexity = O(n) (linear time). Types of Common Time Complexities...
Read more