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

https://algo.monster/problems/binary_tree_right_side_view

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)
1 Like

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;

        var queue = new LinkedList<Node<int>>();
        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
                if (node.right != null) queue.AddFirst(node.right);
                if (node.left != null) queue.AddFirst(node.left);
            }
        }

        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)[0]
	*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>>();
    queue.add(root);
    
    // 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;
            
            // Add all children
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
        
        // Add last node that was seen in the loop
        result.add(lastNode);
    }
    return result;
}

you are welcome

public static List<Integer> binaryTreeRightSideView(Node<Integer> root) {
        // WRITE YOUR BRILLIANT CODE HERE
        Queue<Node<Integer>> q = new LinkedList();
        List<Integer> result = new ArrayList();
        q.add(root);
        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)
                {
                    result.add(n.val);
                }
                if(n.left != null) q.add(n.left);
                if(n.right != null) q.add(n.right);
            }
        }
        return result;
    }

There is a typo in line 14 of the JavaScript solution. It currently says:

res.push(queue[0].val);  // only append the first node we encounter since it's the rightmost

However, we should be getting queue[queue.length - 1] instead.

def binary_tree_right_side_view(root: Node) -> List[int]:
    if not root:
        return []

    res = []
    queue = deque([root])

    while queue:
        res.append(queue[-1].val)

        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return res

dfs solution

def binary_tree_right_side_view(root: Node) -> List[int]:
    rst = []
    def dfs(node, level=0):
        if not node:
            return

        if level >= len(rst):
            rst.append(node.val)
            
        dfs(node.right, level + 1)
        dfs(node.left, level + 1)
    dfs(root)
    return rst