C++: Binary Tree Right Side View

Thought Process

To get the right side view of a binary tree, we can use a modified DFS approach. We traverse the tree in a right-to-left manner, ensuring that the first node encountered at each level is the rightmost node. We maintain a vector to store the rightmost nodes, and we only add a node to the vector if its level matches the current size of the vector. This ensures that we capture the rightmost node at each level efficiently. 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void rightView(TreeNode* root, vector<int> &v,int level){

        if(root==NULL)
            return;

        if(v.size() == level)
            v.push_back(root->val);

        rightView(root->right,v,level+1);
        rightView(root->left,v,level+1);
    }
    vector<int> rightSideView(TreeNode* root) {
        
        vector<int> v;
        if(root == NULL)
            return v;

        rightView(root,v,0);
        return v;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The space used by the recursion stack depends on the height of the tree (h). In the worst case, the space complexity is O(n).

Code copied!