Top View of Binary Tree in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Top View for a Simple Binary Tree

What is the printed top view of the binary tree after running the given code?

DSA C

/*
Binary Tree Structure:
        1
       / \
      2   3
       \   \
        4   5
*/

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

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

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

// Function to print top view
void topView(struct Node* root) {
    if (!root) return;
    int hd = 0;
    int min_hd = 0, max_hd = 0;
    // For simplicity, assume horizontal distance range is -10 to 10
    int top[21] = {0};
    int visited[21] = {0};

    // Queue for level order traversal
    struct Node* queue[100];
    int hdQueue[100];
    int front = 0, rear = 0;

    queue[rear] = root;
    hdQueue[rear] = 10; // offset 10 for index
    rear++;

    while (front < rear) {
        struct Node* temp = queue[front];
        int hd = hdQueue[front];
        front++;

        if (!visited[hd]) {
            top[hd] = temp->data;
            visited[hd] = 1;
            if (hd < min_hd) min_hd = hd;
            if (hd > max_hd) max_hd = hd;
        }

        if (temp->left) {
            queue[rear] = temp->left;
            hdQueue[rear] = hd - 1;
            rear++;
        }
        if (temp->right) {
            queue[rear] = temp->right;
            hdQueue[rear] = hd + 1;
            rear++;
        }
    }

    for (int i = 0; i <= 20; i++) {
        if (visited[i]) {
            printf("%d ", top[i]);
        }
    }
    printf("\n");
}

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

    topView(root);
    return 0;
}

A 1 2 3 4 5

B 2 4 1 3 5

C 4 2 1 3 5

D 2 1 3 5

💡 Hint

Think about which nodes are visible from the top when looking horizontally.

The top view includes nodes 2, 1, 3, and 5 because node 4 is hidden behind node 2 when viewed from the top.

❓ Predict Output

intermediate

Top View Output for a Left Skewed Tree

What is the output of the top view function for this left skewed binary tree?

DSA C

/*
Binary Tree Structure:
    10
    /
   20
   /
  30
*/

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

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

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

void topView(struct Node* root) {
    if (!root) return;
    int hd = 0;
    int min_hd = 0, max_hd = 0;
    int top[21] = {0};
    int visited[21] = {0};

    struct Node* queue[100];
    int hdQueue[100];
    int front = 0, rear = 0;

    queue[rear] = root;
    hdQueue[rear] = 10;
    rear++;

    while (front < rear) {
        struct Node* temp = queue[front];
        int hd = hdQueue[front];
        front++;

        if (!visited[hd]) {
            top[hd] = temp->data;
            visited[hd] = 1;
            if (hd < min_hd) min_hd = hd;
            if (hd > max_hd) max_hd = hd;
        }

        if (temp->left) {
            queue[rear] = temp->left;
            hdQueue[rear] = hd - 1;
            rear++;
        }
        if (temp->right) {
            queue[rear] = temp->right;
            hdQueue[rear] = hd + 1;
            rear++;
        }
    }

    for (int i = 0; i <= 20; i++) {
        if (visited[i]) {
            printf("%d ", top[i]);
        }
    }
    printf("\n");
}

int main() {
    struct Node* root = newNode(10);
    root->left = newNode(20);
    root->left->left = newNode(30);

    topView(root);
    return 0;
}

A 30 20 10

B 10 20 30

C 10

D 20 30 10

💡 Hint

In a left skewed tree, all nodes have decreasing horizontal distance.

The top view shows all nodes because each has a unique horizontal distance: 30 at hd=8, 20 at hd=9, 10 at hd=10.

🔧 Debug

advanced

Identify the Error in Top View Implementation

What error will this code produce when running the top view function on a binary tree?

DSA C

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

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

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

void topView(struct Node* root) {
    if (!root) return;
    int top[5] = {0};
    int visited[5] = {0};

    struct Node* queue[100];
    int hdQueue[100];
    int front = 0, rear = 0;

    queue[rear] = root;
    hdQueue[rear] = 2; // center index
    rear++;

    while (front < rear) {
        struct Node* temp = queue[front];
        int hd = hdQueue[front];
        front++;

        if (!visited[hd]) {
            top[hd] = temp->data;
            visited[hd] = 1;
        }

        if (temp->left) {
            queue[rear] = temp->left;
            hdQueue[rear] = hd - 1;
            rear++;
        }
        if (temp->right) {
            queue[rear] = temp->right;
            hdQueue[rear] = hd + 1;
            rear++;
        }
    }

    for (int i = 0; i < 5; i++) {
        if (visited[i]) {
            printf("%d ", top[i]);
        }
    }
    printf("\n");
}

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

    topView(root);
    return 0;
}

A Array index out of bounds error

B Segmentation fault due to null pointer

C No output printed

D Correct output: 4 2 1 3

💡 Hint

Check the size of arrays and the range of horizontal distances used.

The horizontal distance can go below 0 or above 4, but arrays top and visited have size 5, causing index out of bounds.

🧠 Conceptual

advanced

Understanding Horizontal Distance in Top View

In the top view of a binary tree, what does the horizontal distance (hd) represent?

A The vertical level of the node in the tree

B The distance of the node from the root along the left edges only

C The horizontal offset of the node from the root node, where left child decreases hd by 1 and right child increases hd by 1

D The number of nodes between the root and the current node

💡 Hint

Think about how we assign horizontal distances when traversing left or right.

Horizontal distance is assigned by subtracting 1 when moving left and adding 1 when moving right from the root's hd=0.

🚀 Application

expert

Top View Nodes Count for a Complex Tree

Given the binary tree below, how many nodes will be visible in the top view? Tree structure: 10 / \ 20 30 / \ \ 40 50 60 \ \ 70 80 Choose the correct count of nodes visible in the top view.

A 5

B 6

C 7

D 8

💡 Hint

Count unique horizontal distances with the topmost node at each distance.

Top view nodes are 40 (hd=-2), 20 (hd=-1), 10 (hd=0), 30 (hd=1), 60 (hd=2), 80 (hd=3). Total 6 nodes.

Practice

1. What does the top view of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the top

B. Nodes visible when the tree is viewed from the left side

C. Nodes visible when the tree is viewed from the right side

D. All leaf nodes of the tree

Solution

1. Step 1: Understand the meaning of top view

   The top view of a binary tree shows nodes visible when looking down vertically from above the tree.

2. Step 2: Compare with other views

   Left or right views show nodes from side angles, and leaf nodes are only the bottom nodes, not the top view.

3. Final Answer:

   Nodes visible when the tree is viewed from the top -> Option A

4. Quick Check:

   Top view = nodes seen from above [OK]

Hint: Top view shows nodes visible from above the tree [OK]

Common Mistakes:

• Confusing top view with left or right view
• Thinking top view includes all leaf nodes
• Assuming top view shows all nodes

2. Which data structure is commonly used to find the top view of a binary tree in C?

easy

A. Stack

B. Queue

C. Hash Map

D. Linked List

Solution

1. Step 1: Identify traversal method for top view

   Top view is found using level order traversal, which uses a queue to process nodes level by level.

2. Step 2: Understand role of queue

   Queue helps visit nodes in order from top to bottom and left to right, needed for correct top view.

3. Final Answer:

   Queue -> Option B

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level order traversal in top view [OK]

Common Mistakes:

• Using stack which is for depth-first traversal
• Confusing hash map as traversal structure
• Using linked list instead of queue

3. What is the output top view of the binary tree below?

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

medium

A. [1, 2, 3, 4, 5]

B. [2, 1, 4, 6, 7]

C. [2, 1, 3, 4, 7]

D. [2, 1, 3, 5, 7]

Solution

1. Step 1: Assign horizontal distances

   Assign horizontal distance (HD) from root: root(1) = 0, left child decreases HD by 1, right child increases HD by 1. So, 2 = -1, 3 = 1, 4 = 0, 5 = 2, 6 = 1, 7 = 3.

2. Step 2: Select topmost nodes at each HD

   At HD -1: 2; HD 0: 1 (4 is lower); HD 1: 3 (6 is lower); HD 2: 5; HD 3: 7.

3. Final Answer:

   [2, 1, 3, 5, 7] -> Option D

4. Quick Check:

   Top view nodes by HD = [2,1,3,5,7] [OK]

Hint: Use horizontal distance and pick top nodes [OK]

Common Mistakes:

• Choosing lower nodes instead of top nodes
• Ignoring horizontal distance concept
• Mixing order of nodes in output

4. Consider this C code snippet to print top view of a binary tree:

void topView(Node* root) {
    if (!root) return;
    map topNode;
    queue> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        Node* node = p.first;
        int hd = p.second;
        if (topNode.find(hd) == topNode.end())
            topNode[hd] = node->data;
        if (node->left) q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
    for (auto it : topNode)
        cout << it.second << " ";
}

What is the error in this code?

medium

A. Incorrect horizontal distance calculation

B. Not checking if root is NULL

C. Using C++ STL map and queue in C code

D. Missing return statement in void function

Solution

1. Step 1: Identify language mismatch

   The code uses C++ STL containers like map and queue, but the function is declared in C style which does not support these STL features.

2. Step 2: Check other code parts

   Root NULL check is present, horizontal distance is correctly updated, and void functions do not require return statements.

3. Final Answer:

   Using C++ STL map and queue in C code -> Option C

4. Quick Check:

   C code cannot use C++ STL containers [OK]

Hint: C code can't use C++ STL containers like map or queue [OK]

Common Mistakes:

• Ignoring language differences between C and C++
• Thinking void functions need return
• Assuming horizontal distance logic is wrong

5. You have a binary tree where multiple nodes share the same horizontal distance and level. How should you modify the top view algorithm to always show the leftmost node at that horizontal distance?

hard

A. Store the first node encountered at each horizontal distance during level order traversal

B. Store the last node encountered at each horizontal distance during level order traversal

C. Store nodes with maximum depth at each horizontal distance

D. Store nodes with minimum depth at each horizontal distance but prefer right child first

Solution

1. Step 1: Understand node selection in top view

   Top view shows the first node encountered at each horizontal distance during level order traversal, which naturally picks the leftmost node at that distance.

2. Step 2: Avoid overwriting nodes

   By storing only the first node at each horizontal distance and ignoring later nodes, the leftmost node is preserved.

3. Final Answer:

   Store the first node encountered at each horizontal distance during level order traversal -> Option A

4. Quick Check:

   First node at HD = leftmost node [OK]

Hint: Keep first node per horizontal distance in level order [OK]

Common Mistakes:

• Overwriting with last node instead of first
• Choosing nodes by max depth instead of min
• Preferring right child first breaks leftmost rule