199. Binary Tree Right Side View

Problem Description:

Given the root of a binary tree, return the values of the nodes you can see ordered from top to bottom when standing on the right side of the tree.

Solutions:

Two approaches are presented to solve this problem: Breadth-First Search (BFS) and Depth-First Search (DFS). Both have a time complexity of O(N) and a space complexity of O(N), where N is the number of nodes in the tree.

Solution 1: Breadth-First Search (BFS)

This approach utilizes a queue to perform a level-order traversal. The rightmost node at each level is added to the result.

Algorithm:

1. Initialization: Create an empty list ans to store the results and a queue q to store nodes for processing. Add the root node to the queue if it exists.
2. Level Traversal: While the queue is not empty, do the following:
   • Add the value of the first node (which will be the rightmost node from the previous level) in the queue to ans.
   • Iterate through the number of nodes currently in the queue (the current level's nodes). For each node:
     • Dequeue the node.
     • Add its right child (if it exists) to the queue.
     • Add its left child (if it exists) to the queue.

Code (Python):

from collections import deque
 
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]:
        ans = []
        if not root:
            return ans
        q = deque([root])
        while q:
            ans.append(q[0].val)  # Add the rightmost node from previous level.
            for _ in range(len(q)):
                node = q.popleft()
                if node.right:
                    q.append(node.right)
                if node.left:
                    q.append(node.left)
        return ans

Time and Space Complexity:

• Time Complexity: O(N) - Each node is visited and processed once.
• Space Complexity: O(N) - In the worst case (a complete binary tree), the queue will hold up to N/2 nodes.

Solution 2: Depth-First Search (DFS)**

This approach uses recursion to traverse the tree. The key is to process the right subtree before the left subtree to ensure the rightmost node at each depth is visited first.

Algorithm:

1. Initialization: Create an empty list ans to store the results.
2. Recursive DFS: Implement a recursive function dfs(root, depth):
   • Base Case: If root is None, return.
   • Check Depth: If the current depth is equal to the length of ans, append the current node's value to ans (this means we've reached a new level).
   • Recursive Calls: Recursively call dfs on the right subtree first, then the left subtree.

Code (Python):

class Solution:
    def rightSideView(self, root: TreeNode) -> list[int]:
        ans = []
        def dfs(root, depth):
            if not root:
                return
            if len(ans) == depth:
                ans.append(root.val)
            dfs(root.right, depth + 1)
            dfs(root.left, depth + 1)
        dfs(root, 0)
        return ans
 

Time and Space Complexity:

• Time Complexity: O(N) - Each node is visited and processed once.
• Space Complexity: O(N) - The space complexity is determined by the maximum depth of the recursion stack, which can be O(N) in the worst case (a skewed tree).

Note: The code for other languages (Java, C++, Go, TypeScript, Rust, JavaScript) would follow similar logic and structure but with the appropriate syntax and data structures for each language. The provided problem statement includes these examples.