---
title: Top View of Binary Tree
description: Learn how to print the top view of a binary tree with detailed explanations and code examples in C++, Java, and Python.
author: Team Scaler
category: Data Structures
amphtml: https://www.example.com/top-view-of-binary-tree/amp/
publish_date: 2023-09-11
---

:::section{.main}
## Problem Statement
In a binary tree, the top view refers to the set of nodes that are visible when the tree is observed from the top. Given below a binary tree, the task is to print its top view. The output nodes can be printed in any order.

## Example

### Example Explanation
Imagine you are looking at a binary tree from above, like a bird's-eye view. When you do this, *you want to see the nodes that are the highest at each horizontal position*, which we call the top view. To figure out which nodes to include in the top view, we use something called "horizontal distance."

**Horizontal Distance:** It's like measuring how far to the left or right a node is from the center. If a node is directly above the root, its horizontal distance is 0. If it's to the left of the root, the distance is negative, and if it's to the right, the distance is positive.

In this example, the top view would consist of nodes 4, 2, 1, 3, and 7. These nodes are the highest at their respective horizontal positions when viewed from above. The nodes 8 and 9 are not included in the top view because they are not at the highest position in their respective horizontal distances.

:::section{.main}

### Approach 1

This approach aims to find the top view of a binary tree. The top view of a tree is the set of nodes that would be visible if we look at the tree from directly above. It involves using a queue and a map to keep track of the horizontal distances of nodes.

Here's the step-by-step explanation:

1. **Base Case Check**: If the root of the tree is null, we return, as there are no nodes to process.

2. **Initialization**: We initialize a queue to perform a level-order traversal and a map to keep track of the horizontal distances (`hd`) of nodes.

3. **Setting Initial Horizontal Distance**: We start with the root node and set its horizontal distance (`hd`) as 0. Then, we enqueue it.

4. **Level Order Traversal**:
- While the queue is not empty, we proceed with the following steps:
- Update `hd` with the horizontal distance of the current node (`root->hd`).
- If `hd` is not in the map, it means this is the first node at this horizontal distance. We add it to the map with the value of the current node.
- Enqueue the left child with `hd - 1` if it exists, as it would be to the left of the current node in the top view.
- Enqueue the right child with `hd + 1` if it exists, as it would be to the right of the current node in the top view.
- Dequeue the front element to move on to the next node.

5. **Printing the Top View**:
- After the traversal, the map contains the nodes in the top view along with their horizontal distances. We print the values in ascending order of their horizontal distances.

:::

### Code Implementation (C++)

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

// Structure of binary tree
struct Node {
    Node* left;
    Node* right;
    int hd;
    int data;
};

// function to create a new node
Node* newNode(int key) {
    Node* node = new Node();
    node->left = node->right = NULL;
    node->data = key;
    return node;
}

// function to print the top view of the binary tree
void topView(Node* root) {
    if (root == NULL)
        return;
    queue<Node*> q;
    map<int, int> m;
    int hd = 0;
    root->hd = hd;

    // push node and horizontal distance to queue
    q.push(root);

    while (!q.empty()) {
        hd = root->hd;

        if (m.count(hd) == 0)
            m[hd] = root->data;
        if (root->left) {
            root->left->hd = hd - 1;
            q.push(root->left);
        }
        if (root->right) {
            root->right->hd = hd + 1;
            q.push(root->right);
        }
        q.pop();
        root = q.front();
    }

    cout << "The top view of the tree is : \n";

    for (auto i = m.begin(); i != m.end(); i++) {
        cout << i->second << " ";
    }
}

int main() {
    /* Create the given Binary Tree:
               1
              / \
             2   3
            / \  / \
           4   5 1   7
              /  \
             8   9
    */
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(1);
    root->right->right = newNode(7);
    root->left->right->left = newNode(8);
    root->right->left->right = newNode(9);

    topView(root);
    return 0;
}

### Output

The top view of the tree is : 
4 2 1 3 7 

- **Time Compexity:** O(N * log(N)), where N is the number of nodes in the given tree.
- **Space Complexity:** O(N), As we store nodes in the map and queue.

### Java Implementation

import java.util.*;

// Structure of binary tree
class Node {
    Node left;
    Node right;
    int hd;
    int data;

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

// Class for Top View
public class TopView {
    // function to print the top view of the binary tree
    static void topView(Node root) {
        if (root == null)
            return;
        Queue<Node> q = new LinkedList<>();
        TreeMap<Integer, Integer> m = new TreeMap<>();
        int hd = 0;
        root.hd = hd;

        // push node and horizontal distance to queue
        q.add(root);

        while (!q.isEmpty()) {
            hd = root.hd;

            if (!m.containsKey(hd))
                m.put(hd, root.data);
            if (root.left != null) {
                root.left.hd = hd - 1;
                q.add(root.left);
            }
            if (root.right != null) {
                root.right.hd = hd + 1;
                q.add(root.right);
            }
            q.remove();
            root = q.peek();
        }

        System.out.println("The top view of the tree is : ");
        for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
            System.out.print(entry.getValue() + " ");
        }
    }

    public static void main(String[] args) {
        /* Create the given Binary Tree:
                   1
                  / \
                 2   3
                / \  / \
               4   5 1   7
                  /  \
                 8   9
        */
        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(1);
        root.right.right = new Node(7);
        root.left.right.left = new Node(8);
        root.right.left.right = new Node(9);

        topView(root);
    }
}

### Output

The top view of the tree is : 
4 2 1 3 7 

- **Time Complexity:** O(N * log(N)), where N is the number of nodes in the given tree.
- **Space Complexity:** O(N), as we store nodes in the TreeMap and queue.

## Python Implementation

from collections import deque, OrderedDict

# Structure of binary tree
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.hd = 0
        self.data = key

# Function to print the top view of the binary tree
def top_view(root):
    if root is None:
        return
    q = deque()
    m = OrderedDict()
    hd = 0
    root.hd = hd

    # push node and horizontal distance to queue
    q.append(root)

    while q:
        root = q[0]
        hd = root.hd

        if hd not in m:
            m[hd] = root.data
        if root.left:
            root.left.hd = hd - 1
            q.append(root.left)
        if root.right:
            root.right.hd = hd + 1
            q.append(root.right)
        q.popleft()

    print("The top view of the tree is :")
    for value in m.values():
        print(value, end=" ")

# Create the given Binary Tree
#       1
#      / \
#     2   3
#    / \  / \
#   4   5 1   7
#      /  \
#     8   9
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(1)
root.right.right = Node(7)
root.left.right.left = Node(8)
root.right.left.right = Node(9)

top_view(root)

### Output (Python)

The top view of the tree is :
1 2 3 4 7

- **Time Complexity:** O(N), where N is the number of nodes in the given tree.
- **Space Complexity:** O(N), as we store nodes in the OrderedDict and queue.

## Approach 2

**Approach:** To find the top view of a binary tree, we employ a map to keep track of the vertical distance and depth of each node from the root. This allows us to index nodes based on their vertical distance. If we encounter a node with the same vertical distance again, we compare its depth with the current node at that distance in the map. If the new node has a lower depth, we replace it.

**Algorithm:**

1. Create a map of type `<int, pair<int, int>>` and initialize two variables `d` and `l` to store horizontal and vertical distances from the root respectively.
2. Call the function to print the top view.
3. If the root is null, return from the function (base case).
4. Check if `d` is not present in the map. If not, set `map[d]` to `{root->data, l}`.
5. If `d` is already present and its vertical distance is greater than `l`, update `map[d]` to `{root->data, l}`.
6. Recursively call the function for `(root->left, d-1, l+1, mp)` and `(root->right, d+1, l+1, mp)`.
7. Print the top view of the binary tree using the map.

### Code Implementation (C++):

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

// Structure of binary tree
struct Node {
    Node* left;
    Node* right;
    int data;
};

// function to create a new node
Node* newNode(int key) {
    Node* node = new Node();
    node->left = node->right = NULL;
    node->data = key;
    return node;
}

// function to fill the map
void fillMap(Node* root, int d, int l,
             map<int, pair<int, int>>& m) {
    if (root == NULL)
        return;

    if (m.count(d) == 0) {
        m[d] = make_pair(root->data, l);
    }
    else if (m[d].second > l) {
        m[d] = make_pair(root->data, l);
    }

    fillMap(root->left, d - 1, l + 1, m);
    fillMap(root->right, d + 1, l + 1, m);
}

// function should print the topView of
// the binary tree
void topView(struct Node* root) {
    // map to store the pair of node value and its level
    // with respect to the vertical distance from root.
    map<int, pair<int, int>> m;

    // fillmap(root,vectical_distance_from_root,level_of_node,map)
    fillMap(root, 0, 0, m);

    for (auto it = m.begin(); it != m.end(); it++) {
        cout << it->second.first << " ";
    }
}

// Driver code
int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(1);
    root->right->right = newNode(7);
    root->left->right->left = newNode(8);
    root->right->left->right = newNode(9);

    cout << "Following are nodes in top view of Binary Tree\n";
    topView(root);
    return 0;
}

### Output:

Following are nodes in top view of Binary Tree
4 2 1 3 7 

- **Time complexity:** O(N * log(N)), where N is the number of nodes in the given binary tree with each insertion operation in Map requiring O(log2 N) complexity.
- **Auxiliary Space:** O(N)

### Java Implementation

import java.util.*;

// Structure of binary tree
class Node {
    Node left;
    Node right;
    int data;

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

// Class for Top View
public class TopView {
    static void fillMap(Node root, int d, int l, Map<Integer, AbstractMap.SimpleEntry<Integer, Integer>> m) {
        if (root == null)
            return;

        if (!m.containsKey(d)) {
            m.put(d, new AbstractMap.SimpleEntry<>(root.data, l));
        } else if (m.get(d).getValue() > l) {
            m.put(d, new AbstractMap.SimpleEntry<>(root.data, l));
        }

        fillMap(root.left, d - 1, l + 1, m);
        fillMap(root.right, d + 1, l + 1, m);
    }

    static void topView(Node root) {
        Map<Integer, AbstractMap.SimpleEntry<Integer, Integer>> m = new TreeMap<>();
        fillMap(root, 0, 0, m);

        for (Map.Entry<Integer, AbstractMap.SimpleEntry<Integer, Integer>> entry : m.entrySet()) {
            System.out.print(entry.getValue().getKey() + " ");
        }
    }

    public static void main(String[] args) {
        /* Create the given Binary Tree:
                   1
                  / \
                 2   3
                / \  / \
               4   5 1   7
                  /  \
                 8   9
        */
        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(1);
        root.right.right = new Node(7);
        root.left.right.left = new Node(8);
        root.right.left.right = new Node(9);

        System.out.println("Following are nodes in top view of Binary Tree");
        topView(root);
    }
}

### Output (Java)

Following are nodes in top view of Binary Tree
4 2 1 3 7

- **Time Complexity:** O(N * log(N)), where N is the number of nodes in the given binary tree with each insertion operation in Map requiring O(log2 N) complexity.
- **Space Complexity:** O(N)

### Python Implementation

from collections import deque, OrderedDict

# Structure of binary tree
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.data = key

# Function to fill the map
def fillMap(root, d, l, m):
    if root is None:
        return

    if d not in m:
        m[d] = (root.data, l)
    elif m[d][1] > l:
        m[d] = (root.data, l)

    fillMap(root.left, d - 1, l + 1, m)
    fillMap(root.right, d + 1, l + 1, m)

# Function to print the topView of the binary tree
def topView(root):
    m = OrderedDict()
    fillMap(root, 0, 0, m)

    for value in m.values():
        print(value[0], end=" ")

# Create the given Binary Tree
#       1
#      / \
#     2   3
#    / \  / \
#   4   5 1   7
#      /  \
#     8   9
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(1)
root.right.right = Node(7)
root.left.right.left = Node(8)
root.right.left.right = Node(9)

print("Following are nodes in top view of Binary Tree")
topView(root)

### Output (Python)

Following are nodes in top view of Binary Tree
4 2 1 3 7

- **Time Complexity:** O(N), where N is the number of nodes in the given binary tree.
- **Space Complexity:** O(N)

## Conclusion

- The top view of a binary tree displays nodes visible from a bird's-eye view, using horizontal distance as a measure.
- Approach 1 (C++, Java, Python) involves using a map to store horizontal distances and performing a pre-order traversal to update the map with nodes.
- Approach 2 (C++, Java, Python) utilizes a map to track vertical distance and depth, allowing nodes to be indexed based on vertical distance.
- In both approaches, time complexity is O(N * log(N)), where N is the number of tree nodes.
- The space complexity for both approaches is O(N) due to the storage of nodes in data structures like maps and queues.