Right View of Binary Tree

Problem Statement

Given the root of a binary tree, return the right view of the binary tree. The right view of a binary tree consists of the nodes that are visible when the tree is viewed from the right side.

Examples

Example 1:

Input:
        1
       / \
      2   3
     / \    \
    4   5    6
Output: [1, 3, 6]

Explanation:
From the right side, you can see:
Level 1: Node 1
Level 2: Node 3
Level 3: Node 6

Example 2:

Input:
         1
        / \
       2   3
        \
         4
          \
           5
Output: [1, 3, 4, 5]

Explanation:
The right view includes the last node visible at each level from the right side:

At Level 1: Node 1 is visible.
At Level 2: Node 3 is visible.
At Level 3: Node 4 is visible.
At Level 4: Node 5 is visible.

Example 3:

Input:
        1
         \
          2
           \
            3
             \
              4
Output: [1, 2, 3, 4]

Explanation:
All nodes are visible from the right side.

Different Approaches

1️⃣ Level Order Traversal

Intuition:

The right view of a binary tree consists of nodes visible when the tree is observed from the right side. At each level, the last node encountered during a level order traversal (BFS) represents the rightmost node visible from the right view.

Approach:

1. Level Order Traversal (BFS):
   • Traverse the tree level by level using a queue.
   • For each level, process nodes from left to right.
   • Record the last node encountered at each level (i.e., the last node dequeued in that level).
2. Alternative DFS Approach:
   • Perform a Depth First Search (DFS).
   • Prioritize traversing the right subtree first.
   • Track the maximum depth reached so far, and include the first node encountered at each new depth.

Code:

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

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    // Constructor to initialize the node with a value
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to return the Right view of the binary tree
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;

        // Get the level order traversal of the tree
        vector<vector<int>> levelTraversal = levelOrder(root);

        // Iterate through each level and add the last element to the result
        for (auto level : levelTraversal) {
            res.push_back(level.back());
        }

        return res;
    }

    // Function to return the Left view of the binary tree
    vector<int> leftSideView(TreeNode* root) {
        vector<int> res;

        // Get the level order traversal of the tree
        vector<vector<int>> levelTraversal = levelOrder(root);

        // Iterate through each level and add the first element to the result
        for (auto level : levelTraversal) {
            res.push_back(level.front());
        }

        return res;
    }

private:
    // Function that returns the level order traversal of a Binary tree 
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;

        // Return an empty vector if the tree is empty
        if (!root) {
            return ans;
        }

        // Use a queue to perform level order traversal
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            vector<int> level;

            // Process each node in the current level
            for (int i = 0; i < size; i++) {
                TreeNode* top = q.front();
                level.push_back(top->data);
                q.pop();

                // Enqueue the left child if it exists
                if (top->left != NULL) {
                    q.push(top->left);
                }

                // Enqueue the right child if it exists
                if (top->right != NULL) {
                    q.push(top->right);
                }
            }

            // Add the current level to the result
            ans.push_back(level);
        }

        return ans;
    }
};

int main() {
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(10);
    root->left->left->right = new TreeNode(5);
    root->left->left->right->right = new TreeNode(6);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(10);
    root->right->left = new TreeNode(9);

    Solution solution;

    // Get the Right View traversal
    vector<int> rightView = solution.rightSideView(root);

    // Print the result for Right View
    cout << "Right View Traversal: ";
    for (auto node : rightView) {
        cout << node << " ";
    }
    cout << endl;

    // Get the Left View traversal
    vector<int> leftView = solution.leftSideView(root);

    // Print the result for Left View
    cout << "Left View Traversal: ";
    for (auto node : leftView) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:
  • Traversal: Each node is visited once during BFS, which takes O(N), where N is the number of nodes.
  • Level Processing: Processing all nodes at a level is linear in total: O(N)
  • Overall: O(N)
• Space Complexity:
  • Queue Storage: At most, the queue contains nodes from the largest level of the tree, O(W), where W is the maximum width of the tree.
  • In the worst case, W = O(N) for a skewed tree, but for a balanced tree, W = O(rootof N).
  • Overall: O(W)