Top View of a Binary Tree - Iterative Approach

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given the root of a binary tree, return the top view of the tree. The top view of a binary tree is the set of nodes visible when the tree is viewed from the top. You should return the values of these nodes from left to right, based on their horizontal distance from the root. Use an iterative approach (like level-order traversal) to compute this top view.

Examples❯

Input Tree Top View Output Description
[1, 2, 3, 4, 5, null, 6]
[4, 2, 1, 3, 6] Standard tree with multiple levels; leftmost and rightmost nodes at each level appear in top view
[1]
[1] Single node tree; root itself is the top view
[] [] Empty tree with no nodes returns an empty top view
[1, 2, null, 3, null, 4]
[4, 3, 2, 1] Left-skewed tree; only the leftmost path visible in top view
[1, null, 2, null, 3, null, 4]
[1, 2, 3, 4] Right-skewed tree; every node appears in top view due to unique horizontal distances
[1, 2, 3, 4, null, null, 5, 6]
[6, 4, 2, 1, 3, 5] Complex tree with deep left and right subtrees; top view includes the outermost nodes

Solution❯

Understanding the Problem

The Top View of a binary tree refers to the set of nodes visible when we look at the tree from the top. For each vertical column (based on horizontal distance from the root), we should see only the topmost node — the one that appears first in a top-down traversal.

We’ll solve this using a level-order traversal (BFS) approach, and for each horizontal distance (HD), we record the first node we encounter. This way, we capture the top view from left to right.

Step-by-Step Solution with Example

step 1: Visualize the Tree

Consider the binary tree:


       1
     /       2     3
        /       4 5   6

Here, node 1 is the root. Node 2 is on the left, node 3 is on the right. Node 4 is the right child of 2, and nodes 5 and 6 are the children of 3.

step 2: Define Horizontal Distance

Assign a horizontal distance (HD) to each node:

  • Root (1) has HD = 0
  • Left child decreases HD by 1
  • Right child increases HD by 1

So we get:

  • Node 1: HD = 0
  • Node 2: HD = -1
  • Node 3: HD = +1
  • Node 4: HD = 0
  • Node 5: HD = 0
  • Node 6: HD = +2

step 3: Perform Level-Order Traversal

Use a queue for BFS. Track both node and its HD. Maintain a map where key = HD and value = first node seen at that HD.

Processing in BFS order (top to bottom, left to right):

  1. Visit node 1 (HD=0) → not in map → add
  2. Visit node 2 (HD=-1) → not in map → add
  3. Visit node 3 (HD=1) → not in map → add
  4. Visit node 4 (HD=0) → already in map → skip
  5. Visit node 5 (HD=0) → already in map → skip
  6. Visit node 6 (HD=2) → not in map → add

step 4: Extract and Sort Results

The map now has nodes at each horizontal distance:

  • HD = -1 → Node 2
  • HD = 0 → Node 1
  • HD = 1 → Node 3
  • HD = 2 → Node 6

Sort keys: [-1, 0, 1, 2], then print values in that order: [2, 1, 3, 6]

Edge Cases

Empty Tree

If the tree is empty (root = null), then the top view is simply an empty list.

Single Node Tree

If the tree has only one node (the root), then the top view contains just that one node.

Left-Skewed Tree

Each node only has a left child. Every node will have a unique HD (all negative) and will be visible from the top.

Right-Skewed Tree

Each node only has a right child. Each node gets a unique positive HD and will appear in the top view.

Overlapping Nodes at Same HD

In trees where multiple nodes share the same HD, only the first node encountered in level-order traversal is taken for the top view. This ensures higher nodes (closer to root) are prioritized.

Finally

The top view of a binary tree helps us understand its vertical structure from above. By tracking horizontal distances during a BFS traversal, we efficiently extract the topmost visible node at each vertical level. Always sort the HDs before output to ensure left-to-right ordering.

This method ensures correctness for all types of binary trees — from skewed to balanced and general trees with complex structures.

Algorithm Steps❯

  1. If the tree is empty, return an empty result.
  2. Initialize a queue and enqueue a tuple containing the root node and its horizontal distance (0).
  3. Initialize an empty map (or dictionary) to store the first node encountered at each horizontal distance.
  4. While the queue is not empty, dequeue a tuple (node, hd).
  5. If the horizontal distance hd is not present in the map, record the node's value for that hd.
  6. Enqueue the left child with horizontal distance hd - 1 and the right child with hd + 1 (if they exist).
  7. After processing all nodes, sort the keys of the map and output the corresponding node values as the top view.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

int main() {
    printf("Hello, World from C!\n");
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...