🌱 Keegan's Digital Garden

199. Binary Tree Right Side View

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- we can do either a DFS or BFS 
- go as far down the right subtree as possible, keeping track of the level we are on
- check if the level and size of the results array are equal, if they are then it means we havent inserted a right side node into our array yet
- if they arent equal, ignore the node and keep traversing

🤔What Did I Struggle With?

- a 3 is not reflective of how i did in this question
- i pretty much nailed the question, but i was given a low 'coding mark' since i had to go straight from example/algo explanation to code due to time constraints
- dfs is such a simple algo that pseudocode was almost not necessary but was omission of pseudocode was the reason i failed

💡 Explanation of Solution

same as intuition

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n) since our results vector could be right skewed and we could return a total of n elements

💻 Implementation of Solution (DFS)

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        dfs(root, 0, result);
        return result;
    }
 
private:
    void dfs(TreeNode* node, int depth, vector<int>& result) {
        if (!node) return;
 
        // If this is the first time visiting this depth, add the node's value
        if (depth == result.size()) {
            result.push_back(node->val);
        }
 
        // Recurse to the right first, then the left
        dfs(node->right, depth + 1, result);
        dfs(node->left, depth + 1, result);
    }
};

💻 Implementation of Solution (BFS)

class Solution {
 
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if(!root) return result;
  
        queue<TreeNode*> q;
        q.push(root);
 
        while(!q.empty()) {
            int levelSize = q.size();
 
            for(int i=0; i < levelSize; i++) {
                TreeNode* currentNode = q.front();
                q.pop();
  
                //if its the last node in the current level, add it to result
                if(i == levelSize -1) {
                    result.push_back(currentNode->val);
                }
  
                if(currentNode->left) q.push(currentNode->left);
                if(currentNode->right) q.push(currentNode->right);
            }
        }
        return result;
    }
};

Graph View