Problem Statement:
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Examples:
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation:
Example 2:
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Explanation:
Example 3:
Input: root = [1,null,3]
Output: [1,3]
Example 4:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach
- If the tree is empty, return an empty array.
- Use a queue
qfor level-order traversal (BFS). - For each level:
- Store the number of nodes (
levelSize). - Traverse all nodes at this level.
- Since you push right first, the first node (
i == 0) is the rightmost node of that level → store it inans. - Push
rightchild first, thenleft, to ensure rightmost nodes are visited first in the next level.
- Store the number of nodes (
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(w) Where w is the maximum width of the tree
Dry Run
Function Call: rightSideView(root) where
root = TreeNode(1)
├── left: TreeNode(2)
│ └── right: TreeNode(5)
└── right: TreeNode(3)
└── right: TreeNode(4)
Step 1:
→ Initialize ans = []
→ Initialize q = [1]
Step 2 (First Level):
→ levelSize = 1
→ i = 0
→ curr = 1
→ i == 0 → ans.push(1) → ans = [1]
→ curr.right = 3 → q.push(3)
→ curr.left = 2 → q.push(2)
Step 3 (Second Level):
→ q = [3, 2]
→ levelSize = 2
→ i = 0
→ curr = 3
→ i == 0 → ans.push(3) → ans = [1, 3]
→ curr.right = 4 → q.push(4)
→ curr.left = null
→ i = 1
→ curr = 2
→ curr.right = 5 → q.push(5)
→ curr.left = null
Step 4 (Third Level):
→ q = [4, 5]
→ levelSize = 2
→ i = 0
→ curr = 4
→ i == 0 → ans.push(4) → ans = [1, 3, 4]
→ curr.right = null
→ curr.left = null
→ i = 1
→ curr = 5
→ curr.right = null
→ curr.left = null
Step 5:
→ q = [] → loop ends
Final Result: [1, 3, 4]
root = TreeNode(1)
├── left: TreeNode(2)
│ └── right: TreeNode(5)
└── right: TreeNode(3)
└── right: TreeNode(4)
Step 1:
→ Initialize ans = []
→ Initialize q = [1]
Step 2 (First Level):
→ levelSize = 1
→ i = 0
→ curr = 1
→ i == 0 → ans.push(1) → ans = [1]
→ curr.right = 3 → q.push(3)
→ curr.left = 2 → q.push(2)
Step 3 (Second Level):
→ q = [3, 2]
→ levelSize = 2
→ i = 0
→ curr = 3
→ i == 0 → ans.push(3) → ans = [1, 3]
→ curr.right = 4 → q.push(4)
→ curr.left = null
→ i = 1
→ curr = 2
→ curr.right = 5 → q.push(5)
→ curr.left = null
Step 4 (Third Level):
→ q = [4, 5]
→ levelSize = 2
→ i = 0
→ curr = 4
→ i == 0 → ans.push(4) → ans = [1, 3, 4]
→ curr.right = null
→ curr.left = null
→ i = 1
→ curr = 5
→ curr.right = null
→ curr.left = null
Step 5:
→ q = [] → loop ends
Final Result: [1, 3, 4]
var rightSideView = function(root) {
if (!root) return [];
let ans = [];
let q = [root];
while (q.length) {
let levelSize = q.length;
for (let i = 0; i < levelSize; i++) {
let curr = q.shift();
if (i === 0) {
ans.push(curr.val);
}
if (curr.right) q.push(curr.right);
if (curr.left) q.push(curr.left);
}
}
return ans;
};
def rightSideView(root):
if not root:
return []
ans = []
q = [root]
while q:
level_size = len(q)
for i in range(level_size):
curr = q.pop(0)
if i == 0:
ans.append(curr.val)
if curr.right:
q.append(curr.right)
if curr.left:
q.append(curr.left)
return ans
public List rightSideView(TreeNode root) {
List ans = new ArrayList<>();
if (root == null) return ans;
Queue q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
TreeNode curr = q.poll();
if (i == 0) ans.add(curr.val);
if (curr.right != null) q.add(curr.right);
if (curr.left != null) q.add(curr.left);
}
}
return ans;
}
vector rightSideView(TreeNode* root) {
vector ans;
if (!root) return ans;
queue q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
for (int i = 0; i < levelSize; ++i) {
TreeNode* curr = q.front();
q.pop();
if (i == 0) ans.push_back(curr->val);
if (curr->right) q.push(curr->right);
if (curr->left) q.push(curr->left);
}
}
return ans;
}
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct Queue {
TreeNode** data;
int front, rear, size, capacity;
} Queue;
// Implement queue functions here...
void rightSideView(TreeNode* root, int* result, int* returnSize) {
if (!root) {
*returnSize = 0;
return;
}
Queue* q = createQueue(100);
enqueue(q, root);
int idx = 0;
while (!isEmpty(q)) {
int levelSize = q->size;
for (int i = 0; i < levelSize; i++) {
TreeNode* curr = dequeue(q);
if (i == 0)
result[idx++] = curr->val;
if (curr->right) enqueue(q, curr->right);
if (curr->left) enqueue(q, curr->left);
}
}
*returnSize = idx;
}
public IList RightSideView(TreeNode root) {
List ans = new List();
if (root == null) return ans;
Queue q = new Queue();
q.Enqueue(root);
while (q.Count > 0) {
int levelSize = q.Count;
for (int i = 0; i < levelSize; i++) {
TreeNode curr = q.Dequeue();
if (i == 0) ans.Add(curr.val);
if (curr.right != null) q.Enqueue(curr.right);
if (curr.left != null) q.Enqueue(curr.left);
}
}
return ans;
}
