Top View of Binary Tree in DSA C

Mental Model

We want to see the nodes visible when looking at the tree from above, ignoring nodes hidden behind others.

Analogy: Imagine standing on a balcony looking straight down at a garden with trees; you only see the tops of the trees that are not blocked by others.

       1
      / \
     2   3
      \   \
       4   5

Top view shows nodes: 2 -> 1 -> 3 -> 5

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has right child 4; 3 has right child 5

Goal: Print nodes visible from top view: nodes that appear first at each horizontal distance from root

Step 1: Start at root (1) with horizontal distance (hd) = 0; record node 1 for hd 0

hd_map: {0:1}
Queue: [(1,0)]

Why: Root is always visible from top at hd 0

Step 2: Dequeue (1,0); enqueue left child (2, -1) and right child (3, 1)

hd_map: {0:1}
Queue: [(2,-1), (3,1)]

Why: Left child is one step left (hd -1), right child one step right (hd 1)

Step 3: Dequeue (2,-1); record node 2 for hd -1; enqueue right child (4,0)

hd_map: {-1:2, 0:1}
Queue: [(3,1), (4,0)]

Why: First node at hd -1 is 2; right child 4 is at hd 0 but 1 already recorded

Step 4: Dequeue (3,1); record node 3 for hd 1; enqueue right child (5,2)

hd_map: {-1:2, 0:1, 1:3}
Queue: [(4,0), (5,2)]

Why: First node at hd 1 is 3; enqueue its right child

Step 5: Dequeue (4,0); hd 0 already recorded, skip recording; no children to enqueue

hd_map: {-1:2, 0:1, 1:3}
Queue: [(5,2)]

Why: Node 4 is hidden behind node 1 at hd 0

Step 6: Dequeue (5,2); record node 5 for hd 2; no children

hd_map: {-1:2, 0:1, 1:3, 2:5}
Queue: []

Why: First node at hd 2 is 5

Result:

Top view nodes in order of hd: 2 -> 1 -> 3 -> 5

Annotated Code

DSA C

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

// Node structure for binary tree
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Queue node for BFS storing tree node and horizontal distance
typedef struct QNode {
    Node* treeNode;
    int hd;
    struct QNode* next;
} QNode;

// Queue structure
typedef struct Queue {
    QNode *front, *rear;
} Queue;

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

// Create new queue node
QNode* newQNode(Node* treeNode, int hd) {
    QNode* qnode = (QNode*)malloc(sizeof(QNode));
    qnode->treeNode = treeNode;
    qnode->hd = hd;
    qnode->next = NULL;
    return qnode;
}

// Initialize queue
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

// Enqueue operation
void enqueue(Queue* q, Node* treeNode, int hd) {
    QNode* temp = newQNode(treeNode, hd);
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

// Dequeue operation
QNode* dequeue(Queue* q) {
    if (q->front == NULL) return NULL;
    QNode* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    return temp;
}

// Check if queue is empty
int isEmpty(Queue* q) {
    return q->front == NULL;
}

// Map structure for horizontal distance to node data
typedef struct MapNode {
    int hd;
    int data;
    struct MapNode* next;
} MapNode;

// Insert into map only if hd not present
void insertMap(MapNode** head, int hd, int data) {
    MapNode* curr = *head;
    while (curr != NULL) {
        if (curr->hd == hd) return; // already recorded
        curr = curr->next;
    }
    MapNode* new_map_node = (MapNode*)malloc(sizeof(MapNode));
    new_map_node->hd = hd;
    new_map_node->data = data;
    new_map_node->next = *head;
    *head = new_map_node;
}

// Find min and max hd in map
void findMinMax(MapNode* head, int* min_hd, int* max_hd) {
    *min_hd = INT_MAX;
    *max_hd = INT_MIN;
    MapNode* curr = head;
    while (curr != NULL) {
        if (curr->hd < *min_hd) *min_hd = curr->hd;
        if (curr->hd > *max_hd) *max_hd = curr->hd;
        curr = curr->next;
    }
}

// Get data for given hd
int getData(MapNode* head, int hd) {
    MapNode* curr = head;
    while (curr != NULL) {
        if (curr->hd == hd) return curr->data;
        curr = curr->next;
    }
    return -1; // not found
}

// Print top view of binary tree
void topView(Node* root) {
    if (root == NULL) return;

    Queue* q = createQueue();
    MapNode* hd_map = NULL;

    enqueue(q, root, 0);

    while (!isEmpty(q)) {
        QNode* temp = dequeue(q);
        Node* curr_node = temp->treeNode;
        int hd = temp->hd;
        free(temp);

        // Record first node at this horizontal distance
        insertMap(&hd_map, hd, curr_node->data);

        if (curr_node->left != NULL) enqueue(q, curr_node->left, hd - 1);
        if (curr_node->right != NULL) enqueue(q, curr_node->right, hd + 1);
    }

    int min_hd, max_hd;
    findMinMax(hd_map, &min_hd, &max_hd);

    for (int i = min_hd; i <= max_hd; i++) {
        int val = getData(hd_map, i);
        if (val != -1) {
            printf("%d", val);
            if (i < max_hd) printf(" -> ");
        }
    }
    printf("\n");
}

int main() {
    // Construct tree from dry run
    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;
}

enqueue(q, root, 0);

Start BFS from root with horizontal distance 0

QNode* temp = dequeue(q);

Remove front node from queue to process

insertMap(&hd_map, hd, curr_node->data);

Record first node encountered at this horizontal distance

if (curr_node->left != NULL) enqueue(q, curr_node->left, hd - 1);

Add left child with hd one less

if (curr_node->right != NULL) enqueue(q, curr_node->right, hd + 1);

Add right child with hd one more

findMinMax(hd_map, &min_hd, &max_hd);

Find range of horizontal distances recorded

for (int i = min_hd; i <= max_hd; i++) { int val = getData(hd_map, i); ... }

Print nodes in order from leftmost to rightmost horizontal distance

Output

2 -> 1 -> 3 -> 5

Complexity Analysis

Time: O(n) because we visit each node once during BFS traversal

Space: O(n) for queue and map storing nodes and horizontal distances

vs Alternative: Naive approach might do multiple traversals or sorting; BFS with map is efficient and direct

Edge Cases

Empty tree

No output, function returns immediately

DSA C

if (root == NULL) return;

Tree with single node

Prints the single node as top view

DSA C

enqueue(q, root, 0);

Tree with multiple nodes at same horizontal distance

Only the first node encountered at that hd is recorded and printed

DSA C

if (curr->hd == hd) return; // already recorded

When to Use This Pattern

When asked to print nodes visible from top or bottom view of a binary tree, use BFS with horizontal distance tracking to find first nodes at each horizontal distance.

Common Mistakes

Mistake: Recording all nodes at a horizontal distance instead of only the first one
Fix: Check if horizontal distance is already recorded before inserting new node

Mistake: Using DFS which may not guarantee top view order
Fix: Use BFS to process nodes level by level ensuring first node at hd is recorded

Summary

Prints the nodes visible when looking at the binary tree from above.

Use when you need to find the top view of a binary tree showing nodes not hidden behind others.

Track horizontal distances during BFS and record only the first node at each distance.

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