199. Binary Tree Right Side View Leetcode Solution
Binary Tree Right Side View Leetcode Problem :
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.
Example :
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Binary Tree Right Side View Leetcode Solution :
Constraints :
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Example 1:
- Input: root = [1,null,3]
- Output: [1,3]
Intution :
The code aims to find the right side view of a binary tree, which consists of the values of the nodes that are visible when looking at the tree from the right side. The idea is to perform a level-order traversal using a queue and keep track of the rightmost element at each level.
Approach :
-
-
Initialization:
- Initialize an empty vector ans to store the right side view. Create a queue q for performing a level-order traversal.
- Base Case:
- Check if the input root is nullptr. If true, return an empty vector, as there is no right side view.
- Level-Order Traversal:
- Enqueue the root node into the queue q to start the traversal.
- Begin a while loop that continues until the queue is empty.
- Within the loop:
- Access the rightmost element of the current level by setting temp to the back of the queue (q.back()).
- Add the value of temp to the ans vector, representing the right side view.
- Determine the number of nodes at the current level (n) by getting the size of the queue.
- Iterate through all nodes at the current level using a nested loop:
- Enqueue the left child of the front element of the queue if it exists.
- Enqueue the right child of the front element of the queue if it exists.
- Dequeue the front element to move to the next node in the level.
- Repeat this process until all levels are traversed.
- Return Result:
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
vector< int>ans;
queue< TreeNode*>q;
vector< int> rightSideView(TreeNode* root) {
if(root==nullptr) return {};
q.push(root);
while(!q.empty()){
TreeNode*temp=q.back();
ans.push_back(temp->val);
int n=q.size();
while(n--){
if(q.front()->left) q.push(q.front()->left);
if(q.front()->right) q.push(q.front()->right);
q.pop();
}
}
return ans;
}
};
Java
class Solution {
int maxlevel = 0;
public List< Integer> rightSideView(TreeNode root) {
List< Integer> list = new ArrayList<>();
right(root,1,list);
return list ;
}
void right(TreeNode root,int level,List< Integer> list){
if(root==null){
return ;
}
if(maxlevel< level){
list.add(root.val);
maxlevel=level;
}
right(root.right,level+1,list);
right(root.left,level+1,list);
}
}
Python
from collections import deque
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
queue = deque()
if root is None:
return []
if root.left is None and root.right is None:
return [root.val]
result = []
queue.append(root)
while queue:
child_queue = deque()
prev = -1
while queue:
curr = queue.popleft()
if curr.left is not None:
child_queue.append(curr.left)
if curr.right is not None:
child_queue.append(curr.right)
prev = curr
result.append(prev.val)
queue = child_queue
return resultGet over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment