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 12 / \3 2 34 / \ \5 4 5 6From 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
- Keep a
levelnumber along with the node (the root is level 0). - If
levelequals the current size of the answer, this is the first node reached at this depth. Add its value. - Recurse on the right child first with
level + 1, then the left child withlevel + 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