DSA Series Chapter 11 SOLUTIONS TO ALL 15 TREE TRAVERSAL EXERCISES(C Version)

on


[Follow here] for daily coding insights

DSA Series Chapter 11 

SOLUTIONS TO ALL 15 TREE TRAVERSAL EXERCISES(C Version)

SECTION A – BASIC LEVEL

Q1

Tree:

        A
       / \
      B   C
     / \
    D   E

Preorder: A B D E C
Postorder: D E B C A
Level-Order: A B C D E

Q2

Tree:

        12
       /  \
      7    25
     / \
    3   9

Preorder: 12 7 3 9 25

Q3

        P
       / \
      Q   R
         / \
        S   T

Postorder: Q S T R P

Q4

        X
       / \
      Y   Z
         / \
        M   N

Level-Order: X Y Z M N

Q5

        8
       / \
      3   10
     / \
    1   6

Preorder: 8 3 1 6 10
Postorder: 1 6 3 10 8

SECTION B – INTERMEDIATE LEVEL

Q6

        4
      /   \
     2     7
    / \     \
   1   3     9

Inorder: 1 2 3 4 7 9
Preorder: 4 2 1 3 7 9
Postorder: 1 3 2 9 7 4

Q7

           15
          /  \
        10    20
       / \    /
      5  12  18

Postorder: 5 12 10 18 20 15

Q8

           A
         /   \
        B     C
         \   / \
          D E   F

Level-Order: A B C D E F

Q9

        25
       /  \
      15   40
     / \    \
    10 20    50

Preorder: 25 15 10 20 40 50
Inorder: 10 15 20 25 40 50

Q10

           K
         /   \
        L     M
       / \     \
      N   O     P

Postorder: N O L P M K
Level-Order: K L M N O P

SECTION C – ADVANCED LEVEL

Q11

Given:
Preorder: A B D E C F G
Inorder: D B E A F C G

Constructed tree:

        A
       / \
      B   C
     / \ / \
    D  E F  G

Postorder: D E B F G C A

Q12

           1
         /   \
        2     3
       / \   / \
      4  5  6   7
           \
            8

Preorder: 1 2 4 5 8 3 6 7
Inorder: 4 2 5 8 1 6 3 7
Postorder: 4 8 5 2 6 7 3 1
Level-Order: 1 2 3 4 5 6 7 8

Q13

                H
           /         \
          I           J
        /   \       /   \
       K     L     M     N
            /
           O

Level-Order: H I J K L M N O
Preorder: H I K L O J M N
Postorder: K O L I M N J H

Q14

        90
       /  \
     50    120
      \      \
      60     150
            /
          130

Inorder: 50 60 90 120 130 150
Preorder: 90 50 60 120 150 130
Level-Order: 90 50 120 60 150 130

Q15

          T
        /   \
       R     W
      /     / \
     Q     V   X
      \       /
       S     Y

Preorder: T R Q S W V X Y
Postorder: S Q R V Y X W T
Level-Order: T R W Q V X S Y

1. C Program for Preorder Traversal

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

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

// Preorder Traversal (Root – Left – Right)
void preorder(struct Node* root) {
    if (root == NULL)
        return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

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

    printf("Preorder Traversal: ");
    preorder(root);

    return 0;
}

2. C Program for Inorder Traversal

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Inorder Traversal (Left – Root – Right)
void inorder(struct Node* root) {
    if (root == NULL)
        return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main() {
    struct Node* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);
    root->left->left = createNode(3);
    root->left->right = createNode(7);

    printf("Inorder Traversal: ");
    inorder(root);

    return 0;
}

3. C Program for Postorder Traversal

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Postorder Traversal (Left – Right – Root)
void postorder(struct Node* root) {
    if (root == NULL)
        return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

int main() {
    struct Node* root = createNode(50);
    root->left = createNode(30);
    root->right = createNode(70);
    root->left->left = createNode(20);
    root->left->right = createNode(40);

    printf("Postorder Traversal: ");
    postorder(root);

    return 0;
}

4. C Program for Level-Order Traversal (Breadth-First Search)

This includes a queue implementation using arrays.

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

struct Node {
    int data;
    struct Node *left, *right;
};

// Queue for BFS
struct Node* queue[MAX];
int front = -1, rear = -1;

int isEmpty() {
    return (front == -1 || front > rear);
}

void enqueue(struct Node* x) {
    if (rear == MAX - 1) {
        printf("Queue Overflow\n");
        return;
    }
    if (front == -1) front = 0;
    queue[++rear] = x;
}

struct Node* dequeue() {
    if (isEmpty()) {
        return NULL;
    }
    return queue[front++];
}

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Level-Order Traversal
void levelOrder(struct Node* root) {
    if (root == NULL)
        return;

    enqueue(root);

    while (!isEmpty()) {
        struct Node* current = dequeue();
        printf("%d ", current->data);

        if (current->left)
            enqueue(current->left);
        if (current->right)
            enqueue(current->right);
    }
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);

    printf("Level-Order Traversal: ");
    levelOrder(root);

    return 0;
}


Understood.
You want C programs for the remaining 10 solved exercises (Q6–Q15), exactly in the same style as the earlier programs:

  • Build the tree exactly as per the question

  • Perform required traversals

  • Print the outputs for verification

  • Professional, clean, labelled C code

Below are 10 complete C programs, one for each question from Q6 to Q15.

PROGRAM FOR Q6 — Inorder, Preorder, Postorder

Tree:

        4
      /   \
     2     7
    / \     \
   1   3     9

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* create(int x) {
    struct Node* n = malloc(sizeof(struct Node));
    n->data = x;
    n->left = n->right = NULL;
    return n;
}

void inorder(struct Node* r) {
    if (!r) return;
    inorder(r->left);
    printf("%d ", r->data);
    inorder(r->right);
}

void preorder(struct Node* r) {
    if (!r) return;
    printf("%d ", r->data);
    preorder(r->left);
    preorder(r->right);
}

void postorder(struct Node* r) {
    if (!r) return;
    postorder(r->left);
    postorder(r->right);
    printf("%d ", r->data);
}

int main() {
    struct Node* root = create(4);
    root->left = create(2);
    root->right = create(7);
    root->left->left = create(1);
    root->left->right = create(3);
    root->right->right = create(9);

    printf("Inorder: "); inorder(root);
    printf("\nPreorder: "); preorder(root);
    printf("\nPostorder: "); postorder(root);

    return 0;
}

PROGRAM FOR Q7 — Postorder

           15
          /  \
        10    20
       / \    /
      5  12  18

#include <stdio.h>
#include <stdlib.h>

struct Node { int data; struct Node *left,*right; };

struct Node* create(int x){
    struct Node* n = malloc(sizeof(struct Node));
    n->data=x; n->left=n->right=NULL;
    return n;
}

void postorder(struct Node* r){
    if(!r) return;
    postorder(r->left);
    postorder(r->right);
    printf("%d ", r->data);
}

int main(){
    struct Node* root=create(15);
    root->left=create(10);
    root->right=create(20);
    root->left->left=create(5);
    root->left->right=create(12);
    root->right->left=create(18);

    printf("Postorder: ");
    postorder(root);

    return 0;
}

PROGRAM FOR Q8 — Level Order

           A
         /   \
        B     C
         \   / \
          D E   F

(Using characters)

#include <stdio.h>
#include <stdlib.h>

struct Node { char data; struct Node *left,*right; };

struct Node* create(char x){
    struct Node* n = malloc(sizeof(struct Node));
    n->data=x; n->left=n->right=NULL;
    return n;
}

struct Node* queue[100]; int f=-1,r=-1;

void enqueue(struct Node* x){
    if(r==99) return;
    if(f==-1) f=0;
    queue[++r]=x;
}

struct Node* dequeue(){
    if(f==-1 || f>r) return NULL;
    return queue[f++];
}

int empty(){ return (f==-1 || f>r); }

void level(struct Node* root){
    if(!root) return;
    enqueue(root);
    while(!empty()){
        struct Node* c = dequeue();
        printf("%c ", c->data);
        if(c->left) enqueue(c->left);
        if(c->right) enqueue(c->right);
    }
}

int main(){
    struct Node* root=create('A');
    root->left=create('B');
    root->right=create('C');
    root->left->right=create('D');
    root->right->left=create('E');
    root->right->right=create('F');

    printf("Level Order: ");
    level(root);

    return 0;
}

PROGRAM FOR Q9 — Preorder & Inorder

        25
       /  \
      15   40
     / \    \
    10 20    50

#include <stdio.h>
#include <stdlib.h>

struct Node{ int data; struct Node *left,*right; };

struct Node* create(int x){
    struct Node* n = malloc(sizeof(struct Node));
    n->data=x; n->left=n->right=NULL;
    return n;
}

void preorder(struct Node* r){
    if(!r) return;
    printf("%d ", r->data);
    preorder(r->left);
    preorder(r->right);
}

void inorder(struct Node* r){
    if(!r) return;
    inorder(r->left);
    printf("%d ", r->data);
    inorder(r->right);
}

int main(){
    struct Node* root=create(25);
    root->left=create(15);
    root->right=create(40);
    root->left->left=create(10);
    root->left->right=create(20);
    root->right->right=create(50);

    printf("Preorder: "); preorder(root);
    printf("\nInorder: "); inorder(root);

    return 0;
}

PROGRAM FOR Q10 — Postorder & Level Order

           K
         /   \
        L     M
       / \     \
      N   O     P

#include <stdio.h>
#include <stdlib.h>

struct Node { char data; struct Node *left,*right; };

struct Node* create(char x){
    struct Node* n=malloc(sizeof(struct Node));
    n->data=x; n->left=n->right=NULL;
    return n;
}

void postorder(struct Node* r){
    if(!r) return;
    postorder(r->left);
    postorder(r->right);
    printf("%c ", r->data);
}

struct Node* q[100]; int f=-1,r=-1;

void en(struct Node* x){
    if(r==99) return;
    if(f==-1) f=0;
    q[++r]=x;
}

struct Node* de(){
    if(f==-1 || f>r) return NULL;
    return q[f++];
}

int empty(){ return (f==-1 || f>r); }

void level(struct Node* root){
    if(!root) return;
    en(root);
    while(!empty()){
        struct Node* t=de();
        printf("%c ", t->data);
        if(t->left) en(t->left);
        if(t->right) en(t->right);
    }
}

int main(){
    struct Node* root=create('K');
    root->left=create('L');
    root->right=create('M');
    root->left->left=create('N');
    root->left->right=create('O');
    root->right->right=create('P');

    printf("Postorder: "); postorder(root);
    printf("\nLevel Order: "); level(root);

    return 0;
}

PROGRAM FOR Q11 — Tree Reconstruction & Postorder

Preorder: A B D E C F G
Inorder: D B E A F C G

#include <stdio.h>
#include <stdlib.h>

struct Node{ char data; struct Node *left,*right; };

struct Node* create(char x){
    struct Node* n=malloc(sizeof(struct Node));
    n->data=x; n->left=n->right=NULL;
    return n;
}

// Build tree from preorder & inorder
int search(char inorder[], int start, int end, char value){
    for(int i=start;i<=end;i++)
        if(inorder[i]==value) return i;
    return -1;
}

struct Node* build(char preorder[], char inorder[], int start, int end, int *preIndex){
    if(start > end) return NULL;

    struct Node* node = create(preorder[*preIndex]);
    (*preIndex)++;

    if(start == end) return node;

    int inIndex = search(inorder, start, end, node->data);

    node->left = build(preorder, inorder, start, inIndex-1, preIndex);
    node->right = build(preorder, inorder, inIndex+1, end, preIndex);

    return node;
}

void postorder(struct Node* r){
    if(!r) return;
    postorder(r->left);
    postorder(r->right);
    printf("%c ", r->data);
}

int main(){
    char preorder[]={'A','B','D','E','C','F','G'};
    char inorder[]={'D','B','E','A','F','C','G'};
    int preIndex=0;

    struct Node* root = build(preorder, inorder, 0, 6, &preIndex);

    printf("Postorder: ");
    postorder(root);

    return 0;
}

PROGRAM FOR Q12 — All 4 Traversals

(As tree is larger, only one program)

#include <stdio.h>
#include <stdlib.h>

struct Node{ int data; struct Node *left,*right; };

struct Node* create(int x){
    struct Node* n=malloc(sizeof(struct Node));
    n->data=x; n->left=n->right=NULL;
    return n;
}

void preorder(struct Node* r){
    if(!r) return;
    printf("%d ", r->data);
    preorder(r->left); preorder(r->right);
}

void inorder(struct Node* r){
    if(!r) return;
    inorder(r->left); printf("%d ", r->data); inorder(r->right);
}

void postorder(struct Node* r){
    if(!r) return;
    postorder(r->left); postorder(r->right); printf("%d ", r->data);
}

struct Node* q[100]; int f=-1,rq=-1;

void en(struct Node* x){
    if(rq==99) return;
    if(f==-1) f=0;
    q[++rq]=x;
}

int empty(){ return (f==-1 || f>rq); }

struct Node* de(){ return q[f++]; }

void level(struct Node* r){
    if(!r) return;
    en(r);
    while(!empty()){
        struct Node* c=de();
        printf("%d ", c->data);
        if(c->left) en(c->left);
        if(c->right) en(c->right);
    }
}

int main(){
    struct Node* root=create(1);
    root->left=create(2);
    root->right=create(3);
    root->left->left=create(4);
    root->left->right=create(5);
    root->left->right->right=create(8);
    root->right->left=create(6);
    root->right->right=create(7);

    printf("Preorder: "); preorder(root);
    printf("\nInorder: "); inorder(root);
    printf("\nPostorder: "); postorder(root);
    printf("\nLevel Order: "); level(root);

    return 0;
}

PROGRAM FOR Q13 — 3 Traversals

                H
           /         \
          I           J
        /   \       /   \
       K     L     M     N
            /
           O

#include <stdio.h>
#include <stdlib.h>

struct Node{ char data; struct Node *left,*right; };

struct Node* create(char x){
    struct Node* n = malloc(sizeof(struct Node));
    n->data = x;
    n->left=n->right=NULL;
    return n;
}

void preorder(struct Node* r){
    if(!r) return;
    printf("%c ", r->data);
    preorder(r->left);
    preorder(r->right);
}

void postorder(struct Node* r){
    if(!r) return;
    postorder(r->left);
    postorder(r->right);
    printf("%c ", r->data);
}

struct Node* q[100];
int f=-1,rq=-1;

void en(struct Node* x){ if(rq==99) return; if(f==-1) f=0; q[++rq]=x; }
int empty(){ return (f==-1 || f>rq); }
struct Node* de(){ return q[f++]; }

void level(struct Node* r){
    if(!r) return;
    en(r);
    while(!empty()){
        struct Node* c=de();
        printf("%c ", c->data);
        if(c->left) en(c->left);
        if(c->right) en(c->right);
    }
}

int main(){
    struct Node* H=create('H');
    H->left=create('I');
    H->right=create('J');
    H->left->left=create('K');
    H->left->right=create('L');
    H->left->right->left=create('O');
    H->right->left=create('M');
    H->right->right=create('N');

    printf("Level Order: "); level(H);
    printf("\nPreorder: "); preorder(H);
    printf("\nPostorder: "); postorder(H);

    return 0;
}

PROGRAM FOR Q14 — Inorder, Preorder, Level

#include <stdio.h>
#include <stdlib.h>

struct Node{ int data; struct Node *left,*right; };

struct Node* create(int x){
    struct Node* n=malloc(sizeof(struct Node));
    n->data=x; n->left=n->right=NULL;
    return n;
}

void inorder(struct Node* r){
    if(!r) return;
    inorder(r->left); printf("%d ", r->data); inorder(r->right);
}

void preorder(struct Node* r){
    if(!r) return;
    printf("%d ", r->data);
    preorder(r->left); preorder(r->right);
}

struct Node* q[100]; int f=-1,rq=-1;
void en(struct Node* x){ if(rq==99) return; if(f==-1) f=0; q[++rq]=x; }
int empty(){ return (f==-1 || f>rq); }
struct Node* de(){ return q[f++]; }

void level(struct Node* r){
    en(r);
    while(!empty()){
        struct Node* c=de();
        printf("%d ", c->data);
        if(c->left) en(c->left);
        if(c->right) en(c->right);
    }
}

int main(){
    struct Node* root=create(90);
    root->left=create(50);
    root->right=create(120);
    root->left->right=create(60);
    root->right->right=create(150);
    root->right->right->left=create(130);

    printf("Inorder: "); inorder(root);
    printf("\nPreorder: "); preorder(root);
    printf("\nLevel Order: "); level(root);

    return 0;
}

PROGRAM FOR Q15 — Preorder, Postorder, Level

          T
        /   \
       R     W
      /     / \
     Q     V   X
      \       /
       S     Y

#include <stdio.h>
#include <stdlib.h>

struct Node{ char data; struct Node *left,*right; };

struct Node* create(char x){
    struct Node* n=malloc(sizeof(struct Node));
    n->data=x; n->left=n->right=NULL;
    return n;
}

void preorder(struct Node* r){
    if(!r) return;
    printf("%c ", r->data);
    preorder(r->left);
    preorder(r->right);
}

void postorder(struct Node* r){
    if(!r) return;
    postorder(r->left);
    postorder(r->right);
    printf("%c ", r->data);
}

struct Node* q[100]; int f=-1,rq=-1;
void en(struct Node* x){ if(rq==99) return; if(f==-1) f=0; q[++rq]=x; }
struct Node* de(){ return q[f++]; }
int empty(){ return (f==-1 || f>rq); }

void level(struct Node* r){
    en(r);
    while(!empty()){
        struct Node* c=de();
        printf("%c ", c->data);
        if(c->left) en(c->left);
        if(c->right) en(c->right);
    }
}

int main(){
    struct Node* T=create('T');
    T->left=create('R');
    T->right=create('W');
    T->left->left=create('Q');
    T->left->left->right=create('S');
    T->right->left=create('V');
    T->right->right=create('X');
    T->right->right->left=create('Y');

    printf("Preorder: "); preorder(T);
    printf("\nPostorder: "); postorder(T);
    printf("\nLevel Order: "); level(T);

    return 0;
}

ALSO CHECK 

DS(Data Structure) Python&C Edition

DSA Series Chapter 1 Time & Space Complexity ( C Edition)

DSA Series Chapter 2 Arrays  (C Version)


DSA Series Chapter 2 Arrays  (Python Version)

DSA Series Chapter 3 Strings (C Version)


DSA Series Chapter 3 Strings (Python Version)


DSA Series Chapter 4 Linked Lists (Python Version)


DSA Series Chapter 4 Linked Lists (C Version)


DSA Series Chapter 5 Stacks (Python Version)


DSA Series Chapter 5  Stacks  (C Version)


















DSA Series chapter 11 : Solution for 15 Exercises in Python






Tail Recursion Optimization: How Compilers Convert Recursion Into Iteration


Advanced Recursion: Memoization vs. Tabulation — The Deep Optimization Blueprint for Professionals


Advanced Sorting Algorithms: Merge Sort Internals — Merge Tree, Cache Behavior & Real Cost Analysis


Enjoyed this post? [Follow here] for daily coding insights.

Comments

Post a Comment