SDE - 1

Since the arrays are sorted in non-decreasing order, the smallest element among the three pointers at any moment will always be the smallest in the merged arrays. Leveraging this property, we can optimize our approach as follows:

Initialize three pointers, one for each array.
Compare the current elements at each pointer.
If they are equal, it’s a common element, store it and move all three pointers forward.
Otherwise, move only the pointer pointing to the smallest element.
Repeat the process until at least one array is fully traversed.

Using three pointers – O(n1 + n2 + n3) Time and O(1) Space

Step 1: Use a level order traversal (BFS)
To find the right view, we can perform a level-order traversal of the tree using a queue. This ensures that we visit the nodes level by level from top to bottom.

Why Level-order? This is important because the rightmost node of each level will always be the last node visited at that level.

Step 2: Track the rightmost node at each level
During the level-order traversal, I would keep track of the rightmost node for every level.

As we visit nodes at a level, I will always update the rightmost node with the last node at that level.

How to achieve this? After visiting all nodes of a level, the last node processed will be the rightmost node at that level.

Step 3: Use a queue for level order traversal
Start by enqueueing the root node into a queue.

For each level, dequeue the nodes and:

For each node, enqueue its left and right children (if any).

Keep track of the last node processed at each level as the rightmost node.

Step 4: Edge case handling
Empty Tree: If the root is null, return [] since there is no right view.

Single Node: If the tree has only one node, the right view is that node.

Step 5: Output the right view
After completing the traversal, the last node of each level is stored, and that’s our right view of the tree.