# Binary Tree Right Side View - Breadth First Search / BFS on Tree

Alternatively, we can check index when iterating a level, and only add i == n-1 to the result. This does not require changing appending order for children, which is usually [left, right].

``````    for i in range(n): # iterate all i for a level
node = queue.popleft()
if i == n - 1: # only take last i (rightmost)
result.append(node.val)
``````

We can use the fact that indexing into a list is O(1) time and avoid changing the logic much. Below I just look at the end of the queue at each level to get the rightmost node. Traverse the same way as the previous problems.

def binary_tree_right_side_view(root: Node) → List[int]:
output = []

``````if root is not None:
queue = deque([root])

while queue: #[ ]
n = len(queue) # 1
rightmost_node = queue[-1]
output.append(rightmost_node.val) #[1,3,6,7]

for _ in range(n): # 0
curr = queue.popleft() # 7

for child in [curr.left,curr.right]: # n,n
if child is not None:
queue.append(child)
return output
``````

Is it bad that I can’t think of the solution myself, but once I read the solution code I get it instantly?

It’s totally normal.

c# using LinkedList as FIFO Deque

``````    public static List<int> BinaryTreeRightSideView(Node<int> root)
{
var res = new List<int>();
if (root == null) return res;

queue.AddFirst(root);  // at least one element in the queue to kick start bfs

while (queue.Count > 0)
{  // as long as there is element in the queue
int n = queue.Count;  // number of nodes in current level
res.Add(queue.Last.Value.val);  // only append the first node we encounter since it's the rightmost

// dequeue each node in the current level
for (int i = 0; i < n; i++)
{
var node = queue.Last.Value;
queue.RemoveLast();
// we add right children first so it'll pop out of the queue first
}
}

return res;
}
``````

c# using Queue, wasnt familiar with Queue yet in c# so used LinkedList Before.

``````    public static List<int> BinaryTreeRightSideView(Node<int> root)
{
var res = new List<int>();
if (root == null) return res;

var queue = new Queue<Node<int>>();
queue.Enqueue(root);  // at least one element in the queue to kick start bfs

while (queue.Count > 0)
{  // as long as there is element in the queue
int n = queue.Count;  // number of nodes in current level
res.Add(queue.Peek().val);  // only append the first node we encounter since it's the rightmost

// dequeue each node in the current level
for (int i = 0; i < n; i++)
{
var node = queue.Dequeue();
// we add right children first so it'll pop out of the queue first
if (node.right != null) queue.Enqueue(node.right);
if (node.left != null) queue.Enqueue(node.left);
}
}

return res;
}
``````

I think the real reason is ‘we are ordinary’.

for any Go people

``````type NodeQueue []Node

func (q *NodeQueue) Enqueue(n Node) {
*q = append(*q, n)
}

func (q *NodeQueue) Dequeue() Node {
el := (*q)
*q = (*q)[1:]

return el
}

func binaryTreeRightSideView(root *Node) []int {
result := []int{}

if root == nil {
return result
}

var q NodeQueue
q.Enqueue(*root)

for len(q) > 0 {
size := len(q)
level := []int{}

for i := 0; i < size; i++ {
current := q.Dequeue()

level = append(level, current.val)

if current.left != nil {
q.Enqueue(*current.left)
}
if current.right != nil {
q.Enqueue(*current.right)
}
}

result = append(result, level[len(level)-1])
}

return result
}

func main() {
root := Node{1, nil, nil}
root.left = &Node{2, nil, nil}
root.right = &Node{3, nil, nil}
root.left.left = &Node{4, nil, nil}
root.left.right = &Node{5, nil, nil}
root.right.right = &Node{6, nil, nil}
root.left.left.right = &Node{7, nil, nil}
root.left.right.right = &Node{8, nil, nil}

fmt.Println(zigZagTraversal(&root))
}
``````

NOTE - in main it should be calling `binaryTreeRightSideView` not `zigZagTraversal` - thats a typo

To continue on with the previous patterns in the previous questions. We can also just use a variable to keep track of the last Node. Whichever is the last seen in the loop when traversing through the nodes in the current level, is the right most node. See below in Java.

public static List binaryTreeRightSideView(Node root) {
if (root == null) {
return List.of();
}

``````    List<Integer> result = new ArrayList<>();

// Initialize bfs
var queue = new ArrayDeque<Node<Integer>>();

// Continue while queue is not empty
while (!queue.isEmpty()) {
// Keep track of current number of nodes in level
int n = queue.size();

// Use variable to keep track of last node that is removed in loop
Integer lastNode = null;

// Go through all nodes in level
for (int i = 0; i < n; i++) {
// Get node in end
var current = queue.remove();

// Update last Node
lastNode = current.val;

if (current.left != null) {
}
if (current.right != null) {
}
}

// Add last node that was seen in the loop
}
return result;
}
``````

you are welcome

``````public static List<Integer> binaryTreeRightSideView(Node<Integer> root) {
// WRITE YOUR BRILLIANT CODE HERE
List<Integer> result = new ArrayList();
while(!q.isEmpty()){
int size = q.size();
for(int i = 0; i < size; i++){
Node<Integer> n = q.remove();
if(n == null) continue;
if( i == size - 1)
{
}
``````res.push(queue.val);  // only append the first node we encounter since it's the rightmost
However, we should be getting `queue[queue.length - 1]` instead.