On this page

Binary Tree Right Side View

Given the root of a binary tree, imagine standing on the right side of it. Return the values of the nodes you can see, ordered from top to bottom.

Constraints:

  • The number of nodes is in the range [0, 100].
  • -100 <= Node.val <= 100

Intuition

1 1
2 / \
3 2 3
4 / \ \
5 4 5 6

From the right you see 1, 3, 6. At each depth you see one node: the rightmost node at that level. Node 3 hides node 2, and node 6 hides nodes 4 and 5.

Two natural ways to get this:

  • BFS: the right side view is the last node of every level.
  • DFS, right first: visit the right child before the left. The first node reached at a new depth is the rightmost one at that depth.

Approach: DFS, Right Child First

  1. Keep a level number along with the node (the root is level 0).
  2. If level equals the current size of the answer, this is the first node reached at this depth. Add its value.
  3. Recurse on the right child first with level + 1, then the left child with level + 1.

level == ans.size() is a neat way to ask "have I already recorded this depth?". Since the right subtree is explored before the left, the first node at any depth is the rightmost one. Use the BFS approach if you prefer: process the level and take the last node.

Code

class Solution {
void dfs(TreeNode* node, int level, vector<int>& ans) {
if (node == nullptr) return;
if (level == (int)ans.size()) ans.push_back(node->val);
dfs(node->right, level + 1, ans);
dfs(node->left, level + 1, ans);
}
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
dfs(root, 0, ans);
return ans;
}
};

Complexity

Time: O(n)

Every node is visited once.

Space: O(h)

Recursion stack depth equals the tree height. A BFS version would use O(w) for the queue instead.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"From the right side you see exactly one node per depth, the rightmost one. I do a DFS that visits the right child before the left child and carries the current level. If the level equals the current size of my answer list, I have not recorded this depth yet, so this node is the first at its depth, which makes it the rightmost. I add it, then recurse right and then left. The alternative is a level order traversal where I take the last node of each level. DFS takes O of n time and O of h space."
Next TopicBinary Tree Left Side View