Problem overview
The method rightSideView receives the root of a binary tree and returns a vector<int>: the values you would see standing on the tree's right side, from the top level to the bottom one. From there you see exactly one node per level, the rightmost one. An empty tree gives an empty vector.
The lesson provides the TreeNode struct, which has an int val and two pointers, left and right, that are null when the child is missing.
In the first example the tree is [1,2,3,NULL,5,NULL,4]. Level 0 is just 1, level 1 is 2 and 3, and level 2 is 5 and 4. The rightmost nodes are 1, 3 and 4, so the answer is [1,3,4]. In the second example, [1,2,3,4], the node 4 is the only one on level 2. It hangs from the left child 2, yet nothing stands to its right, so it is visible and the answer is again [1,3,4].
Approach: walk the tree one level at a time
The tempting shortcut is to follow right pointers from the root. It fails as soon as the right subtree is shallower than the left one: for [1,2,3,4] it returns [1,3] and misses the 4. The question is about levels, not about right children, so the algorithm should group nodes by level.
A queue does that. Start with the root in the queue. At the beginning of each round the queue holds exactly one level. Count its nodes, take that many out from the front, and push each one's children, left first, at the back. Those children wait there for the next round. Within a round the nodes leave from left to right, so the last node taken out is the rightmost of its level, and that is the value to record.
On the first example the rounds look like this (the queue contents were printed from a run):
| Round | Queue size at the start | Nodes taken out | Recorded |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 2 | 2, 3 | 3 |
| 3 | 2 | 5, 4 | 4 |
Step by step
- Create the result. An empty
vector<int>namedresultcollects one value per level. - Return early for an empty tree. The queue needs a first node, and a null root has none. Returning the empty
resultis the correct answer. - Create the queue and push the root. A
queue<TreeNode*>hands nodes back in the order they came in, which is what makes the visit go level by level. - Loop while the queue isn't empty. Each pass of this loop handles one whole level.
- Store the level's size.
int levelSize = q.size()is read once, before any child is pushed. - Loop over exactly that many nodes. The children pushed during this loop belong to the next level, and counting up to
levelSizekeeps the loop from touching them. - Take the next node with
front(), then remove it withpop().pop()returns nothing, so the read has to come first. - Record the last node of the level. When
i == levelSize - 1, pushnode->valintoresult. - Push the left child if it exists.
- Push the right child if it exists. Left before right keeps every level in left-to-right order.
- Return
resultonce the queue is empty.
The solution in C++
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* node = q.front();
q.pop();
if (i == levelSize - 1) {
result.push_back(node->val);
}
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
return result;
}
};
The C++ details worth a closer look:
- The queue stores pointers. A
queue<TreeNode*>holds addresses of nodes, not copies, so pushing a child is cheap and the nodes stay where they are in the tree. q.size()is unsigned. It returns asize_t. Storing it in anintis fine here because a tree has at most 100 nodes, and it makes the comparisoni < levelSizecompare two signed values.- Null pointers are false.
if (!root)andif (node->left)test a pointer directly: a null pointer counts as false and any other pointer as true. front()andpop()are separate.front()returns a reference to the first element and does not remove it.pop()removes it and returns nothing. Callingfront()on an empty queue is undefined behaviour, which the loop condition prevents.
Complexity
Time: O(n) for n nodes. Every node is pushed once and popped once, and each does a constant amount of work.
Space: O(n). The queue holds at most two neighbouring levels at a time, and a level can contain about half of all the nodes, as in a complete tree. The result adds one value per level, which is smaller still.
Edge cases and common mistakes
- Empty tree. Without the
!rootcheck,q.push(root)would put a null pointer in the queue andnode->valwould dereference it. With the check, the empty tree returns[]. - Following only right children. For
[1,2,3,4]that gives[1,3], while the correct answer is[1,3,4]. - Recording the first node of a level. Testing
i == 0instead ofi == levelSize - 1produces the left side view:[1,2,5]for the first example instead of[1,3,4]. - A single node. The tree
[7]has one level with one node, which is also its last, so the answer is[7]. - A tree that is a left-leaning chain. The tree
[1,2,NULL,3,NULL,4]has one node per level, so every node is visible and the answer is[1,2,3,4]. - Duplicate values. Values may repeat, and that doesn't matter: the algorithm works with nodes and positions, never with values.
Testing
[1,2,3,NULL,5,NULL,4]gives[1,3,4].[1,2,3,4]gives[1,3,4].[]gives[].[7]gives[7].[1,2,NULL,3,NULL,4]gives[1,2,3,4].[1,2,3,4,5,6,7](a full tree) gives[1,3,7].
