# Solution For Binary Tree Right Side View

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.

Example 1:
Input: root = [1,2,3,null,5,null,4] Output: [1,3,4]

Example 2:
Input: root = [1,null,3] Output: [1,3]

Example 3:
Input: root = [] Output: []

Approach:

We can solve this problem using BFS (Breadth First Search) technique. The idea is to traverse the tree level by level and always keep the last node value of each level. So, the rightmost nodes will be visible from the right side of the binary tree.

Algorithm:
1. Create a list named result to store the right-side view of the binary tree.
2. Check if the given root is null or not.
3. If the root is null, then return the empty list result.
4. Initialize the queue with the root node.
5. Loop through the queue till it is empty:
a. initialize the size equal to the length of the queue.
b. Traverse each node level-wise from left to right.
c. Check if the node is the last node for that level, then appent that node’s value to the result list.
d. If the left child of the node exists, then append it to the queue.
e. If the right child of the node exists, then append it to the queue.
6. Finally return the result list, which contains the right-side view of the binary tree.

Code:

Here is the implementation of the algorithm in Python:

def rightSideView(root):
result = [] if root is None:
return result

``````queue = [root]
while queue:
size = len(queue)
for i in range(size):
node = queue.pop(0)
if i == size-1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

return result
``````

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the number of nodes in the binary tree. We traverse each node only once.

Space Complexity:

The space complexity of the above algorithm is O(n), where n is number of nodes in the binary tree. In the worst case, the queue can have all the nodes of the last level. So, the space complexity will be O(n).

This is the detailed solution of the Binary Tree Right Side View problem on Leetcode.

## Step by Step Implementation For Binary Tree Right Side View

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List rightSideView(TreeNode root) {
// result list
List result = new ArrayList<>();

// base case
if (root == null) {
return result;
}

// level order traversal using a queue

while (!queue.isEmpty()) {
int size = queue.size();

// iterate through all nodes of current level
for (int i = 0; i < size; i++) {
TreeNode curr = queue.remove();

// add last node of current level to result
if (i == size - 1) {
}

// add left and right child to queue
if (curr.left != null) {
}
if (curr.right != null) {
}
}
}

return result;
}
}```
```This is my solution for the leetcode problem binary-tree-right-side-view. Output should only consist of exact code with comments and nothing else.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
# Base case
if not root:
return []

# Initialize a list to store the right side view
right_side_view = []

# Do a breadth first search
queue = [root]
while queue:
# Get the size of the current level
size = len(queue)

# Iterate over all the nodes in the current level
for i in range(size):
# Get the node at the front of the queue
node = queue.pop(0)

# If this is the last node of the current level, add it to the right side view
if i == size - 1:
right_side_view.append(node.val)

# Add the left and right child nodes of the current node to the queue
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

return right_side_view```
```/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
// base case:
if (!root) {
return [];
}

// initialize our results array
const results = [];

// create a queue to help us do a breadth first traversal
const queue = [root];

// as long as there are nodes in the queue
while (queue.length) {
// get the number of nodes at the current level
const levelSize = queue.length;

// iterate over the nodes at the current level
for (let i = 0; i < levelSize; i++) {
// get the current node
const currentNode = queue.shift();

// if this is the last node in the level, add it to the results
if (i === levelSize - 1) {
results.push(currentNode.val);
}

// if the current node has a left child, add it to the queue
if (currentNode.left) {
queue.push(currentNode.left);
}

// if the current node has a right child, add it to the queue
if (currentNode.right) {
queue.push(currentNode.right);
}
}
}

// return the results
return results;
};```
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector rightSideView(TreeNode* root) {
// Result vector
vector result;

// Base case
if(root == nullptr) {
return result;
}

// Queue for BFS
queue q;
q.push(root);

while(!q.empty()) {
// Get the size of the current level
int size = q.size();

// Iterate over all the nodes of the current level
for(int i = 0; i < size; i++) {
TreeNode* curr = q.front();
q.pop();

// Add the last node of the current level to the result
if(i == size - 1) {
result.push_back(curr->val);
}

// Add the child nodes of the current node to the queue
if(curr->left) {
q.push(curr->left);
}
if(curr->right) {
q.push(curr->right);
}
}
}

return result;
}
};```
```public IList RightSideView(TreeNode root) {
// create a list to store the right-most values
List rightMostValues = new List();

// create a queue to store the nodes at each level
Queue nodes = new Queue();

// add the root node to the queue
nodes.Enqueue(root);

// while there are still nodes in the queue
while (nodes.Count > 0)
{
// create a list to store the nodes at the current level
List currentLevel = new List();

// loop through all of the nodes in the queue
while (nodes.Count > 0)
{
// remove the first node from the queue and add it to the current level list
TreeNode node = nodes.Dequeue();
}

// add the right-most value of the current level to the rightMostValues list

// loop through all of the nodes in the current level list
for (int i = 0; i < currentLevel.Count; i++)
{
// if the left child exists, add it to the queue
if (currentLevel[i].left != null)
{
nodes.Enqueue(currentLevel[i].left);
}

// if the right child exists, add it to the queue
if (currentLevel[i].right != null)
{
nodes.Enqueue(currentLevel[i].right);
}
}
}

// return the list of right-most values
return rightMostValues;
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]