Different views of a Binary Tree.

Some Properties of Binary Trees

Let's understand some properties of the binary tree required to tackle the problems related to the view of binary trees.

Every node has at most two children.
Every child is inclined to 45° with the horizontal line dividing the node which means the left child will be at -45° and the right child will be at +45°.

Top View

We need to print the nodes of the tree which are visible from the top

As you can see in the above example we need to print the nodes which are first in the vertical line

Intuition --> intuition is pretty clear we need to traverse in a level order but at the same time we need a vertical line and we can use a map to ensure that every line is mapped with the first element it encounters.

Implementation --> For the implementation we will follow the level order traversal and use a map to map an element to its line vertically.

Edge cases -->There is no major edge case except one that if the root is null then we will not see anything so an empty list.

vector<int> getTopView(TreeNode<int> *root) {
    map<int,int> ump;
    vector<int> ans;
    if(root == nullptr) return ans;
    queue<pair<TreeNode<int>*, int>> q;
    q.push({root, 0});
    while(!q.empty()){
        TreeNode<int> *node = q.front().first;
        int level = q.front().second;
        q.pop();
        if(ump.find(level) == ump.end()){
            ump[level] = node->val;
        }
        if(node->left != nullptr){
            q.push({node->left, level - 1});
        }
        if(node->right != nullptr){
            q.push({node->right, level+1});
        }
    }
    for(auto it : ump){
        ans.push_back(it.second);
    }
    return ans;
}

Bottom View

We need to print the nodes of the tree which are visible from the bottom,

As you can see in the above example we need to print the nodes which are at last in any vertical line.

Intuition --> intuition is pretty clear we need to traverse in a level order but at the same time we need a vertical line and we can use a map to ensure that every line is mapped with the last element it encounters.

Implementation --> For the implementation we will follow the level order traversal and use a map to map an element to its line vertically.

Edge cases --> In case of overlapping nodes you can print any of those or according to the question. If the root is null then we will not see anything so an empty list.

vector<int> bottomView(BinaryTreeNode<int> * root){
    map<int,int> ump;
    queue<pair<BinaryTreeNode<int>*, int>> q;
    vector<int> ans;
    if(root == nullptr) return ans;
    q.push({root,0});
    while(!q.empty()){
        auto it = q.front();
        q.pop();
        BinaryTreeNode<int> *node = it.first;
        int level = it.second;
        ump[level] = node->data;
        if(node->left) q.push({node->left, level-1});
        if(node->right) q.push({node->right, level+1});
    }
    for(auto it : ump){
        ans.push_back(it.second);
    }
    return ans;
}

Left View

we need to print the elements of the tree which are visible from the left side

In the above picture nodes 5, 7, 14 and 25 are visible from the left and the remaining nodes will be covered.

Intuition --> intuition is pretty clear we need to traverse in a level order or any order but at the same time we need a max level and we can print the first node we get in any level.

Implementation --> For the implementation we will follow the preorder traversal.

Edge cases --> In case of overlapping nodes you can print any of those or according to the question. If the root is null then we will not see anything so an empty list.

void leftview(BinaryTreeNode<int> *root, int level, int &maxlevel){
    if(root == nullptr){
        return;
    }
    if(maxlevel < level){
        cout << root->data << " ";
        maxlevel = level;
    }
    leftview(root->left, level+1, maxlevel);
    leftview(root->right, level+1, maxlevel);
}

void printLeftView(BinaryTreeNode<int> *root) {
    int maxlevel = 0;
    leftview(root, 1, maxlevel);
}

Right View

we need to print the elements of the tree which are visible from the right side.

In the above picture nodes 44, 51, 65 and 26 are visible from the right and the remaining nodes will be covered.

Intuition --> intuition is pretty clear we need to traverse in a level order or any order but at the same time we need a max level and we can print the last node we get in any level.

Implementation --> For the implementation we will follow the preorder traversal.

Edge cases --> In case of overlapping nodes you can print any of those or according to the question. If the root is null then we will not see anything so an empty list.

void rightview(BinaryTreeNode<int> *root, int level, int &maxlevel, vector<int> &ans){
    if(root == nullptr){
        return;
    }
    if(maxlevel < level){
        ans.push_back(root->data);
        maxlevel = level;
    }
    rightview(root->right, level+1, maxlevel, ans);
    rightview(root->left, level+1, maxlevel, ans);
}
vector<int> printRightView(BinaryTreeNode<int>* root) {
    int maxlevel = 0;
    vector<int> ans;
    rightview(root, 1, maxlevel, ans);
    return ans;
}

Diagonal View

we need to print the elements of the tree which are visible from any diagonal here in this example I am doing the bottom-right but I guess after this discussion you can easily modify the code for the top-right, top-left, and bottom-left as well.

In the above picture nodes 4, 6 and 3 are visible from the bottom-right and the remaining nodes will be covered.

Intuition --> intuition is pretty clear we need to traverse in a level order or any order but at the same time, we need a max level. we need to make our level a little inclined and biased towards the right elements so that our level rather than being horizontal gets inclined by 45° so in implementation, we won't increase our level while traversing g in right considering it as the level is the same and then we will print the last element in every level

Implementation --> For the implementation we will follow the preorder traversal.

Edge cases --> In case of overlapping nodes you can print any of those or according to the question. If the root is null then we will not see anything so an empty list.

void solve(BinaryTreeNode<int> *root, int level, int &maxlevel, vector<int> &ans){
    if(root == nullptr) return;
    solve(root->right, level, maxlevel, ans);
    if(maxlevel <= level){
        ans.push_back(root->data);
        maxlevel = maxlevel+1;
    }
    solve(root->left, level+1, maxlevel, ans);
}
vector<int> bottomRightView(BinaryTreeNode<int>* root) {
    vector<int> ans;
    if(root == nullptr) return ans;
    int maxlevel = 0;
    solve(root, 0, maxlevel, ans);
    sort(ans.begin(), ans.end());
    return ans;
}