Top View of Binary Tree: Implementation in Cpp, Java & Python

Pseudo Code

function DFS(root, hd, level, map):
    if root is null:
        return
    if hd is not in map:
        map[hd] = root.val
    DFS(root.left, hd - 1, level + 1, map)
    DFS(root.right, hd + 1, level + 1, map)

function topView(root):
    map = {}
    DFS(root, 0, 0, map)
    return sorted(map.values())

C++

#include <iostream>
#include <map>
#include <vector>
using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

void DFS(Node* root, int hd, map<int, int>& topViewMap) {
    if (!root) return;
    
    if (topViewMap.find(hd) == topViewMap.end()) {
        topViewMap[hd] = root->val;
    }
    
    DFS(root->left, hd - 1, topViewMap);
    DFS(root->right, hd + 1, topViewMap);
}

vector<int> topView(Node* root) {
    map<int, int> topViewMap;
    DFS(root, 0, topViewMap);
    
    vector<int> result;
    for (auto& pair : topViewMap) {
        result.push_back(pair.second);
    }
    
    return result;
}

int main() {
    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);
    cout << "Top view of the tree: ";
    for (int val : result) {
        cout << val << " ";
    }

    return 0;
}

Java

import java.util.*;

class BinaryTree {
    static class Node {
        int val;
        Node left, right;
        Node(int x) {
            val = x;
            left = right = null;
        }
    }
    static void DFS(Node root, int hd, Map<Integer, Integer> topViewMap) {
        if (root == null) return;
        
        if (!topViewMap.containsKey(hd)) {
            topViewMap.put(hd, root.val);
        }

        DFS(root.left, hd - 1, topViewMap);
        DFS(root.right, hd + 1, topViewMap);
    }

    static List<Integer> topView(Node root) {
        Map<Integer, Integer> topViewMap = new TreeMap<>();
        DFS(root, 0, topViewMap);
        
        return new ArrayList<>(topViewMap.values());
    }

    public static void main(String[] args) {
       
        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);

        List<Integer> result = topView(root);
        System.out.print("Top view of the tree: ");
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Python

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

def DFS(root, hd, map):
    if not root:
        return
    if hd not in map:
        map[hd] = root.val
    DFS(root.left, hd - 1, map)
    DFS(root.right, hd + 1, map)

def topView(root):
    map = {}
    DFS(root, 0, map)
    return [map[hd] for hd in sorted(map)]

# Example Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print("Top view of the tree:", topView(root))

Explanation

• Traverses the tree in a recursive manner. At every node, we see if its horizontal distance (hd) is known before. If not, we put it into topViewMap.
• Starts DFS from the root node and returns the top view by gathering values from the topViewMap ordered according to their horizontal distance.
• Starts the tree, calls the topView function, and prints.

Output

Top view of the tree: [4, 2, 1, 3, 7]

2. Using BFS (Breadth-First Search)

Here, we apply BFS to traverse the binary tree level by level with horizontal distances in a queue. We make sure that we only retain the first node found at each horizontal distance.

Algorithm

• Create a queue and begin BFS at the root node with horizontal distance 0.
• For every node, mark its value at the horizontal distance if not previously marked.
• Enqueue left child and right child with new horizontal distances.
• Following BFS, select nodes from the map according to horizontal distance.

Pseudo Code

function BFS(root):
    if root is null:
        return []
    queue = [(root, 0)]  # (node, horizontal_distance)
    map = {}
    while queue is not empty:
        node, hd = dequeue(queue)
        if hd is not in map:
            map[hd] = node.val
        if node.left is not null:
            enqueue(queue, (node.left, hd - 1))
        if node.right is not null:
            enqueue(queue, (node.right, hd + 1))
    return sorted(map.values())

C++

#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

    map<int, int> topViewMap;
    queue<pair<Node*, int>> q; 
    q.push({root, 0});

    while (!q.empty()) {
        Node* node = q.front().first;
        int hd = q.front().second;
        q.pop();

        if (topViewMap.find(hd) == topViewMap.end()) {
            topViewMap[hd] = node->val;
        }

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

    vector<int> result;
    for (auto& pair : topViewMap) {
        result.push_back(pair.second);
    }

    return result;
}

int main() {
    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);
    cout << "Top view of the tree: ";
    for (int val : result) {
        cout << val << " ";
    }

    return 0;
}

Java

import java.util.*;

class BinaryTree {
    static class Node {
        int val;
        Node left, right;
        Node(int x) {
            val = x;
            left = right = null;
        }
    }

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

        Map<Integer, Integer> topViewMap = new TreeMap<>();
        Queue<Map.Entry<Node, Integer>> queue = new LinkedList<>();
        queue.offer(new AbstractMap.SimpleEntry<>(root, 0));

        while (!queue.isEmpty()) {
            Map.Entry<Node, Integer> entry = queue.poll();
            Node node = entry.getKey();
            int hd = entry.getValue();

            if (!topViewMap.containsKey(hd)) {
                topViewMap.put(hd, node.val);
            }

            if (node.left != null) queue.offer(new AbstractMap.SimpleEntry<>(node.left, hd - 1));
            if (node.right != null) queue.offer(new AbstractMap.SimpleEntry<>(node.right, hd + 1));
        }

        return new ArrayList<>(topViewMap.values());
    }

    public static void main(String[] args) {
        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);

        List<Integer> result = topView(root);
        System.out.print("Top view of the tree: ");
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Python

from collections import deque

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

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

    queue = deque([(root, 0)])  # (node, horizontal_distance)
    top_view_map = {}

    while queue:
        node, hd = queue.popleft()

        if hd not in top_view_map:
            top_view_map[hd] = node.val

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

    return [top_view_map[hd] for hd in sorted(top_view_map)]

# Example Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print("Top view of the tree:", BFS(root))

Explanation

• We utilize a queue to do level-order traversal of the tree. Every node also has its horizontal distance (hd) with it.
• A map (TreeMap in Java) keeps a record of the first node encountered at each horizontal distance so the topmost node is preserved.
• Left and right children of the nodes are added to the queue with their new horizontal distances.
• Once BFS is done, top view nodes are removed from the map in horizontal direction and are returned.

Output

Top view of the tree: [4, 2, 1, 3, 7]

3. Optimized Solution Using BFS

Here we try to optimize the BFS algorithm to exactly get O(n) time complexity. This can be done by performing no additional operation and by visiting each node once and storing results immediately in the right order.

Algorithm

• Insert the root node and its horizontal displacement (0) into the queue.
• For each node it meets, if its horizontal distance does not exist in the map, add it as the highest node.
• Shift to the left child and the right child by adjusting the horizontal distances for them.
• Once BFS is done, get the output from the map sorted by horizontal distance.

Pseudo Code

function OptimizedBFS(root):
    if root is null:
        return []
    queue = [(root, 0)]
    map = {}
    while queue is not empty:
        node, hd = dequeue(queue)
        if hd is not in map:
            map[hd] = node.val
        enqueue(queue, (node.left, hd - 1)) if node.left is not null
        enqueue(queue, (node.right, hd + 1)) if node.right is not null
    return sorted(map.values())

C++

#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

    map<int, int> topViewMap;  
    queue<pair<Node*, int>> q;  
    q.push({root, 0});

    while (!q.empty()) {
        Node* node = q.front().first;
        int hd = q.front().second;
        q.pop();

        if (topViewMap.find(hd) == topViewMap.end()) {
            topViewMap[hd] = node->val;
        }

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

    vector<int> result;
    for (auto& pair : topViewMap) {
        result.push_back(pair.second);
    }

    return result;
}

int main() {
    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 = optimizedBFS(root);
    cout << "Top view of the tree: ";
    for (int val : result) {
        cout << val << " ";
    }

    return 0;
}

Java

import java.util.*;

class BinaryTree {
    static class Node {
        int val;
        Node left, right;
        Node(int x) {
            val = x;
            left = right = null;
        }
    }

    static List<Integer> optimizedBFS(Node root) {
        if (root == null) return new ArrayList<>();

        Map<Integer, Integer> topViewMap = new TreeMap<>();
        Queue<Map.Entry<Node, Integer>> queue = new LinkedList<>();
        queue.offer(new AbstractMap.SimpleEntry<>(root, 0));

        while (!queue.isEmpty()) {
            Map.Entry<Node, Integer> entry = queue.poll();
            Node node = entry.getKey();
            int hd = entry.getValue();

            if (!topViewMap.containsKey(hd)) {
                topViewMap.put(hd, node.val);
            }
            
            if (node.left != null) queue.offer(new AbstractMap.SimpleEntry<>(node.left, hd - 1));
            if (node.right != null) queue.offer(new AbstractMap.SimpleEntry<>(node.right, hd + 1));
        }

        return new ArrayList<>(topViewMap.values());
    }

    public static void main(String[] args) {
        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);

        List<Integer> result = optimizedBFS(root);
        System.out.print("Top view of the tree: ");
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

Python

from collections import deque

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

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

    queue = deque([(root, 0)])  # (node, horizontal_distance)
    top_view_map = {}

    while queue:
        node, hd = queue.popleft()

        if hd not in top_view_map:
            top_view_map[hd] = node.val

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

    return [top_view_map[hd] for hd in sorted(top_view_map)]

# Example Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print("Top view of the tree:", OptimizedBFS(root))

Explanation

• The tree is visited breadth-first by using a queue in which each node is visited along with its horizontal distance (hd).
• The head node for every horizontal distance is stored in the topViewMap.
• Left and right children of the given node are inserted into the queue together with their own horizontal distances (hd - 1 for left child, hd + 1 for right child).
• Once all the nodes have been processed, top view is formed by sorting topViewMap according to horizontal distance and returning the values.

Output

Top view of the tree: [4, 2, 1, 3, 7]

Below are the space and time complexity of every approach:

In conclusion, the top view of binary tree gives a distinct insight by presenting the nodes that are visible from above the tree. We discussed three ways to address this problem: DFS, BFS, and an optimized BFS. The DFS method relies on recursion, whereas BFS ensures level-order traversal with tracking horizontal distance. The optimized BFS enhances performance with effective queue and map operations. All algorithms ensure that the top view nodes are properly captured. The BFS-based algorithms, specifically the optimized version, are both O(n) time and space complexity, optimal and ideal for big trees.

1. Why is BFS applied to the Top View problem?

BFS is best suited for the Top View problem since it travels through the tree level by level, looking at the topmost node at every horizontal distance.

2. In what way does DFS differ from BFS in this problem?

DFS traverses the tree depth-first and BFS level-by-level. BFS is superior to discover the topmost node for any horizontal distance in the tree.

3. Is it possible to optimize the BFS any further?

The optimized BFS with optimization is already of O(n) time complexity by visiting each node once and keeping horizontal distances optimally. Optimal space for optimization is low.

4. Is DFS applicable to solve this problem?

Yes, DFS can be applied to solve the top view problem by maintaining horizontal distances and recursion.