- 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; }};