# LeetCode - 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.

Problem statement taken from: https://leetcode.com/problems/binary-tree-right-side-view

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: []
``````

Constraints:

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

### Explanation

The problem can be solved using PostOrder traversal or Level order traversal. Let's explore the Level order traversal using queues.

#### Level order traversal

We have explored level order traversal using both recursion and iterative approach in our previous blog post LeetCode - Binary Tree Level Order Traversal

Let's use the iterative approach and check the algorithm first.

``````- if root == NULL
- return {}

- initialize queue<TreeNode*> q
push root q.push(root)

- initialize vector<int> result
int queueSize, i

- loop while !q.empty()
- set queueSize = q.size()

- loop for i = queueSize; i > 0; i--
- set node = q.front()
- q.pop()

- if i == queueSize
- result.push_back(node->val)

- if node->right != NULL
- q.push(node->right)

- if node->left != NULL
- q.push(node->left)

- end for loop
- end while loop

- return result
``````

The time complexity of the above approach is O(n), and the space complexity is O(n).

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if(root == NULL) {
return {};
}

queue<TreeNode*> q;
q.push(root);

vector<int> result;
int queueSize, i;

while(!q.empty()) {
queueSize = q.size();

for(i = queueSize; i > 0; i--) {
TreeNode* node = q.front();
q.pop();

if(i == queueSize) {
result.push_back(node->val);
}

if(node->right != NULL) {
q.push(node->right);
}

if(node->left != NULL) {
q.push(node->left);
}
}
}

return result;
}
};``````

#### Golang solution

``````func rightSideView(root *TreeNode) []int {
if root == nil {
return []int{}
}

queue := []*TreeNode{root}

result := []int{}
queueSize, i := 0, 0
var node *TreeNode

for len(queue) != 0 {
queueSize = len(queue)

for i = queueSize; i > 0; i-- {
node = queue[0]
queue = queue[1:]

if i == queueSize {
result = append(result, node.Val)
}

if node.Right != nil {
queue = append(queue, node.Right)
}

if node.Left != nil {
queue = append(queue, node.Left)
}
}
}

return result
}``````

#### Javascript solution

``````var rightSideView = function(root) {
if(root == null) {
return [];
}

let queue = [root];
let result = [];
let queueSize = 0, i = 0;
let node;

while(queue.length > 0 ) {
queueSize = queue.length;

for(i = queueSize; i > 0; i--) {
node = queue.shift();

if(i == queueSize) {
result.push(node.val);
}

if(node.right != null) {
queue.push(node.right);
}

if(node.left != null) {
queue.push(node.left);
}
}
}

return result;
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

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

Step 1: if root == NULL
root -> 1
false

Step 2: queue<TreeNode*> q
q.push(root)
q = [1]

Step 3: vector<int> result
int queueSize, i

Step 4: loop while(!q.empty())
!q.empty() = true

queueSize = q.size()
= 1

loop for i = queueSize; i > 0; i--
i = 1
1 > 0
true

node = q.front()
= ->1

q.pop()
q = []

if i == queueSize
1 == 1
true

result.push_back(q->val)
result.push_back(1)
result = [1]

if node->right != NULL
node->right = ->3
true

q.push(node->right)
q.push(->3)
q = [3]

if node->left != NULL
node->left = ->2
true

q.push(node->right)
q.push(->2)
q = [3, 2]

i--
i = 0

for i > 0
0 > 0
false

Step 5: loop while(!q.empty())
!q.empty() = true

queueSize = q.size()
= 2

loop for i = queueSize; i > 0; i--
i = 2
2 > 0
true

node = q.front()
= ->3

q.pop()
q = [2]

if i == queueSize
2 == 2
true

result.push_back(q->val)
result.push_back(3)
result = [1, 3]

if node->right != NULL
node->right = ->4
true

q.push(node->right)
q.push(->4)
q = [2, 4]

if node->left != NULL
NULL != NULL
false

i--
i = 1

loop for i > 0
1 > 0
true

node = q.front()
= ->2

q.pop()
q = [4]

if i == queueSize
1 == 2
false

if node->right != NULL
node->right = ->5
true

q.push(node->right)
q.push(->5)
q = [4, 5]

if node->left != NULL
NULL != NULL
false

i--
i = 0

loop for i > 0
0 > 0
false

Step 6: loop while(!q.empty())
!q.empty() = true

queueSize = q.size()
= 2

loop for i = queueSize; i > 0; i--
i = 2
2 > 0
true

node = q.front()
= ->4

q.pop()
q = [5]

if i == queueSize
2 == 2
true

result.push_back(q->val)
result.push_back(4)
result = [1, 3, 4]

if node->right != NULL
NULL != NULL
false

if node->left != NULL
NULL != NULL
false

i--
i = 1

loop for i > 0
1 > 0
true

node = q.front()
= ->5

q.pop()
q = []

if i == queueSize
1 == 2
false

if node->right != NULL
NULL != NULL
false

if node->left != NULL
NULL != NULL
false

i--
i = 0

loop for i > 0
0 > 0
false

Step 7: loop while(!q.empty())
!q.empty() = false
q = []

Step 8: return result

We return the answer as [1, 3, 4].
``````