Different Type Of View in Binary Tree
Akash Kandasamy
1649
CBinary TreeC++Interview

Different Type of Veiws in Binary Tree:

  1. Left View
  2. Right View
  3. Top View
  4. Bottom View

Right View:

  • Approach : do a level order traversal and push in left most ie 0th element of each lvl;
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return {};
        queue<TreeNode * > q;
        q.push(root);
        vector<int> ans;
        while(!q.empty()){
            int s = q.size();
            for(int i=0;i<s;i++){
                TreeNode * node = q.front();q.pop();
                if(node->right) q.push(node->right); // see here that we inserting a right node first;
                if(node->left) q.push(node->left);
                if(i == 0) ans.push_back(node->val);
            }
        }
        
        return ans;
    }

Left View:

  • Approach : same as right view but instead of inserting the right node we insert theleft node.

Top View:

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

struct Node
{
    int key;
    Node *left, *right;
    Node(int key){
        this->key = key;
        this->left = this->right = nullptr;
    }
};

void dfs(Node* root, int dist, int level, auto &map){
    if (root == nullptr) return;
    if (map.find(dist) == map.end() || level < map[dist].second) map[dist] = { root->key, level };
    dfs(root->left, dist - 1, level + 1, map);
    dfs(root->right, dist + 1, level + 1, map);
}
 
int main()
{
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->right = new Node(4);
    root->right->left = new Node(5);
    root->right->right = new Node(6);
    root->right->left->left = new Node(7);
    root->right->left->right = new Node(8);
    map<int, pair<int, int>> map;
    dfs(root,0,0,map);

    for (auto it: map) cout << it.second.first << " ";
    return 0;
}

Bottom View:

void dfs(Node* root, int dist, int level, auto &map){
    if (root == nullptr) return;
    if (map.find(dist) == map.end() || level >= map[dist].second) map[dist] = { root->key, level }; // only change is level condition reverses.
    dfs(root->left, dist - 1, level + 1, map);
    dfs(root->right, dist + 1, level + 1, map);
}
Comments (1)