Print Nodes in Top View of Binary Tree

Introduction to Binary Trees and the Top View Concept

Binary trees are a fundamental data structure in computer science, consisting of a root node and two child nodes (left and right). These trees are widely used in various algorithms and applications due to their efficient traversal and search capabilities.

The top view of a binary tree is the set of nodes visible when the tree is viewed from the top. In other words, it represents the leftmost and rightmost nodes at each level or horizontal distance from the root. The top view is an important concept in tree visualization and analysis, as it provides a concise and informative representation of the tree‘s structure.

Imagine you‘re standing above a binary tree and looking down on it. The top view would show you the nodes that are visible from this vantage point, without any obstructions from the nodes below. This view can be particularly useful in applications where you need to quickly understand the overall structure and distribution of nodes in the tree.

Approaches to Solving the Top View Problem

There are several approaches to solving the problem of printing the nodes in the top view of a binary tree. Let‘s explore the most common ones:

DFS (Depth-First Search) Approach

The Depth-First Search (DFS) approach involves traversing the binary tree in a depth-first manner, keeping track of the horizontal distance of each node from the root. The idea is to use a map (or dictionary) to store the first node encountered at each horizontal distance, as this node will be the topmost node at that distance.

The DFS algorithm works as follows:

Initialize a map to store the first node encountered at each horizontal distance.
Perform a DFS traversal of the binary tree, keeping track of the current horizontal distance.
For each node visited, check if the current horizontal distance is already present in the map. If not, add the node to the map.
Recursively call the DFS function for the left and right child nodes, updating the horizontal distance accordingly.
After the DFS traversal is complete, extract the nodes from the map in the order of their horizontal distances and add them to the result list.

The time complexity of the DFS approach is O(n * log n), where n is the number of nodes in the binary tree, due to the sorting of the map‘s keys. The space complexity is O(n), as we use a map to store the top nodes at each horizontal distance.

BFS (Breadth-First Search) Approach

The Breadth-First Search (BFS) approach uses a queue to perform a level-order traversal of the binary tree. This approach is similar to the DFS approach, but it ensures that the topmost node at each horizontal distance is visited before any other node at the same distance.

The BFS algorithm works as follows:

Initialize a queue to store the nodes along with their horizontal distances.
Initialize a map to store the first node encountered at each horizontal distance.
Start the BFS traversal by enqueuing the root node with a horizontal distance of 0.
While the queue is not empty, dequeue a node and its corresponding horizontal distance.
If the current horizontal distance is not yet present in the map, add the node‘s value to the map.
Enqueue the left child with a horizontal distance of the current distance minus 1, and the right child with a horizontal distance of the current distance plus 1.
After the BFS traversal is complete, extract the nodes from the map in the order of their horizontal distances and add them to the result list.

The time complexity of the BFS approach is also O(n * log n), as we need to sort the map‘s keys to get the nodes in the correct order. The space complexity is O(n), as we use a queue and a map to store the nodes and their horizontal distances.

Optimized BFS Approach

While the BFS approach is more efficient than the DFS approach, we can further optimize the solution by taking advantage of the properties of the top view.

The key observation is that the top view only includes the leftmost and rightmost nodes at each horizontal distance. This means that we can keep track of the minimum and maximum horizontal distances encountered during the traversal, and then populate the result list based on these values.

The optimized BFS algorithm works as follows:

Initialize a queue to store the nodes along with their horizontal distances.
Initialize a map to store the first node encountered at each horizontal distance.
Initialize variables to track the minimum and maximum horizontal distances.
Start the BFS traversal by enqueuing the root node with a horizontal distance of 0.
While the queue is not empty, dequeue a node and its corresponding horizontal distance.
Update the minimum and maximum horizontal distances as needed.
If the current horizontal distance is not yet present in the map, add the node‘s value to the map.
Enqueue the left child with a horizontal distance of the current distance minus 1, and the right child with a horizontal distance of the current distance plus 1.
After the BFS traversal is complete, create a result list with a size equal to the number of unique horizontal distances (max – min + 1).
Populate the result list by traversing the map from the minimum to the maximum horizontal distance and adding the corresponding node values.

The time complexity of the optimized BFS approach is O(n), as we only need to traverse the map once to populate the result list. The space complexity is also O(n), as we use a queue and a map to store the nodes and their horizontal distances.

Detailed Walkthrough of the Optimized BFS Approach

Let‘s go through a step-by-step example to understand the optimized BFS approach in more detail.

Consider the following binary tree:

We start by initializing the queue with the root node (1) and its horizontal distance (0).
We also initialize the map to store the first node encountered at each horizontal distance, and the variables to track the minimum and maximum horizontal distances.
We dequeue the root node (1) from the queue and check if its horizontal distance (0) is already present in the map. Since it‘s not, we add the node‘s value (1) to the map.
We then enqueue the left child (2) with a horizontal distance of -1, and the right child (3) with a horizontal distance of 1.
We continue the BFS traversal, dequeuing nodes and updating the map and the minimum/maximum horizontal distances as needed.
After the traversal is complete, the map will contain the following entries:
- Horizontal distance -1: 2
- Horizontal distance 0: 1
- Horizontal distance 1: 3
- Horizontal distance 2: 4
- Horizontal distance 3: 7
We then create a result list with a size equal to the number of unique horizontal distances (max – min + 1 = 5).
We populate the result list by traversing the map from the minimum horizontal distance (min = -1) to the maximum horizontal distance (max = 3), and adding the corresponding node values to the list.
The final result list will be: [4, 2, 1, 3, 7].

This optimized BFS approach ensures that the time complexity is O(n), as we only need to traverse the map once to populate the result list. The space complexity is also O(n), as we use a queue and a map to store the nodes and their horizontal distances.

Practical Applications and Use Cases

The top view of a binary tree has several practical applications and use cases:

Information Visualization: The top view can be used to visualize the overall structure and distribution of nodes in a binary tree. This can be particularly useful in applications where data is represented as a tree-like structure, such as file systems, organizational charts, or decision trees.
Network Analysis: In the context of network analysis, the top view of a binary tree can be used to represent the connectivity and reachability of nodes in a network. This can be useful for tasks like identifying critical nodes, detecting bottlenecks, or analyzing network resilience.
Decision Support Systems: In decision-making processes, the top view of a binary tree can be used to represent the decision space and the possible outcomes. This can help decision-makers quickly understand the overall structure of the problem and identify the most important factors or alternatives.
Spatial Data Representation: The top view of a binary tree can be used to represent and analyze spatial data, such as geographic information or sensor networks. The horizontal distances in the top view can correspond to spatial coordinates, allowing for efficient visualization and analysis of spatial relationships.
Compression and Indexing: The top view of a binary tree can be used as a compact representation of the tree‘s structure, which can be useful for compression or indexing purposes. This can be particularly relevant in applications where the tree-like data needs to be stored or transmitted efficiently.
Algorithmic Optimization: The top view of a binary tree can be used as an intermediate step in various tree-based algorithms, such as finding the lowest common ancestor or performing range queries. By leveraging the top view, these algorithms can be optimized for better performance.

These are just a few examples of the practical applications of the top view of a binary tree. As you can see, this concept has a wide range of use cases across different domains, making it an important and versatile tool in computer science and data analysis.

Coding Implementations in Popular Programming Languages

Now, let‘s take a look at sample code implementations of the optimized BFS approach to print the nodes in the top view of a binary tree, in several popular programming languages.

Python

from collections import deque

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def top_view(root):
    if not root:
        return []

    queue = deque([(root, 0)])
    top_nodes = {}
    min_distance = float(‘inf‘)

    while queue:
        node, distance = queue.popleft()
        min_distance = min(min_distance, distance)

        if distance not in top_nodes:
            top_nodes[distance] = node.data

        if node.left:
            queue.append((node.left, distance - 1))
        if node.right:
            queue.append((node.right, distance + 1))

    return [top_nodes[key] for key in sorted(top_nodes.keys())]

Java

import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int val) {
        data = val;
        left = right = null;
    }
}

class GfG {
    static ArrayList<Integer> topView(Node root) {
        if (root == null)
            return new ArrayList<>();

        Queue<Pair> queue = new LinkedList<>();
        Map<Integer, Integer> topNodes = new TreeMap<>();
        int minDistance = Integer.MAX_VALUE;

        queue.offer(new Pair(root, 0));

        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            Node node = current.node;
            int distance = current.dist;
            minDistance = Math.min(minDistance, distance);

            if (!topNodes.containsKey(distance)) {
                topNodes.put(distance, node.data);
            }

            if (node.left != null) {
                queue.offer(new Pair(node.left, distance - 1));
            }
            if (node.right != null) {
                queue.offer(new Pair(node.right, distance + 1));
            }
        }

        ArrayList<Integer> result = new ArrayList<>(topNodes.values());
        return result;
    }

    static class Pair {
        Node node;
        int dist;

        Pair(Node node, int dist) {
            this.node = node;
            this.dist = dist;
        }
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};

vector<int> topView(Node* root) {
    if (!root)
        return {};

    queue<pair<Node*, int>> q;
    map<int, int> topNodes;
    int minDistance = INT_MAX;

    q.push({root, 0});

    while (!q.empty()) {
        auto [node, distance] = q.front();
        q.pop();
        minDistance = min(minDistance, distance);

        if (!topNodes.count(distance)) {
            topNodes[distance] = node->data;
        }

        if (node->left) {
            q.push({node->left, distance - 1});
        }
        if (node->right) {
            q.push({node->right, distance + 1});
        }
    }

    vector<int> result;
    for (auto [_, value] : topNodes) {
        result.push_back(value);
    }
    return result;
}

int main() {
    // Create a sample binary tree
    //     1
    //    / \
    //   2   3
    //  / \ / \
    // 4  5 6  7
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    vector<int> result = topView(root);
    for (int i : result) {
        cout << i << " ";
    }
    return 0;
}

C


using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;
    public Node(int val) {
        data = val;
        left = right = null;
    }
}

class GfG {
    static List<int> TopView(Node root) {
        if (root == null)
            return new List<int>();

        Queue<(Node, int)> queue = new Queue<(Node, int)>();
        Dictionary<int, int> topNodes = new Dictionary<int, int>();
        int minDistance = int.MaxValue;

        queue.Enqueue((root, 0));

        while (queue.Count > 0) {
            var (node, distance) = queue.Dequeue();
            minDistance = Math.Min(minDistance, distance);

            if (!topNodes.ContainsKey(distance)) {
                topNodes[distance] = node.data;
            }

            if (node.left != null) {
                queue.Enqueue((node.left, distance - 1));
            }
            if (node.right != null) {
                queue.Enqueue((node.right, distance + 1));
            }
        }

        List<int> result = new List<int>();
        foreach (var (_, value) in topNodes) {
            result.Add(value);
        }
        return result;
    }

    static voi