Top View Of A Binary Tree



Program to find the top view of a binary tree

#include<iostream>
#include<queue>
#include<vector>
#include<stack>

using namespace std;

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

void TopView (Node * root) {

    if (root == nullptr)
       return;

    int hd_left = 0;  // Horizontal distance to the left of root from root.
    int hd_right = 0; // Horizontal distance to the right of root from root.

    stack<int> stk_left_nodes; // Keeps data of nodes to the left in the top view.
    vector<int> vec_right_nodes; // Keeps data of nodes to the right in the top view.

    queue<pair<Node *,int>> q;
    q.push(make_pair(root,0));

    while (!q.empty()) {

        Node* current = q.front().first;
        int dist = q.front().second;
        q.pop();

        if (dist < hd_left) {
            stk_left_nodes.push(current->data);
            hd_left = dist;
        } else if (dist > hd_right) {
            vec_right_nodes.push_back(current->data);
            hd_right = dist;
        }

        // Check if the current node has a left child
        if (current->left) {
            q.push(make_pair(current->left, dist - 1));
        }

        // Check if the current node has a right child
        if (current->right) {
            q.push(make_pair(current->right, dist + 1));
        }
    }

    cout << "Nodes in the top view : ";
    // Print the nodes to the left
    while (!stk_left_nodes.empty()) {
        cout << stk_left_nodes.top() << " ";
        stk_left_nodes.pop();
    }
    
    // Print root data
    cout << root->data << " ";

    // Print the nodes to the right
    for (const auto& data : vec_right_nodes) {
        cout << data << " " ;       
    }
}

int main() {

/* Constructed binary tree is
               9
             /   \
            5     16
          /  \   /  \
         3   7  12   18
            / \       \
           6   8      25
                     /  \
                    20  36
*/
    Node node_6 (6, nullptr, nullptr);
    Node node_8 (8, nullptr, nullptr);
    Node node_12 (12, nullptr, nullptr);
    Node node_20 (20, nullptr, nullptr);
    Node node_36 (36, nullptr, nullptr);
    Node node_25 (25, &node_20, &node_36);
    Node node_3 (3, nullptr, nullptr);
    Node node_7 (7, &node_6, &node_8);
    Node node_5 (5, &node_3, &node_7);
    Node node_18 (18, nullptr, &node_25);
    Node node_16 (16, &node_12, &node_18);
    Node root (9, &node_5, &node_16);

    TopView (&root);

    return 0;
}

Output

Nodes in the top view : 3 5 9 16 18 25 36



Copyright (c) 2019-2022, Algotree.org.
All rights reserved.