Coding Interview Questions | Binary Tree Right Side View

February 3rd, 2024

Binary Tree Right Side View Problem Introduction:

This summary will talk about my solution to the binary tree right side view problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

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.

How do you solve the Binary Tree Right Side View Problem using Breadth-First Search?

Solution:

function rightSideView(root: TreeNode | null): number[] {
  // At each level, return the value of the right most node
  if (!root) {
    return [];
  }

  const nodeQueue: { depth: number; node: TreeNode }[] = [
    { depth: 0, node: root },
  ];
  const output = [];
  const visitedLevelSet = new Set<number>();

  while (nodeQueue.length > 0) {
    const { depth, node: currentNode } = nodeQueue.shift()!;

    if (!visitedLevelSet.has(depth)) {
      output.push(currentNode.val);
      visitedLevelSet.add(depth);
    }

    if (currentNode.right) {
      nodeQueue.push({ node: currentNode.right, depth: depth + 1 });
    }

    if (currentNode.left) {
      nodeQueue.push({ node: currentNode.left, depth: depth + 1 });
    }
  }

  return output;
}

Binary Tree Right Side View Solution Summary:

Below is a breakdown of the key aspects of the solution for the Binary Tree Right Side View problem seen above:

1. Breadth-First Traversal: The algorithm employs a breadth-first traversal using a queue to explore the nodes in the tree, level by level. It starts from the root and processes nodes in a top-down manner.

2. Queue Structure: The algorithm uses a queue (nodeQueue) to keep track of nodes along with their respective depths in the binary tree. The queue initially contains the root node with a depth of 0.

3. Visited Level Set: To ensure only the rightmost node at each level is considered, the algorithm utilizes a set (visitedLevelSet) to keep track of the visited depths. If a node at a certain depth has been processed, its children are skipped.

4. Node Processing: At each step, the algorithm checks if the current depth has been visited. If not, it adds the value of the rightmost node at that depth to the output array. The right child is enqueued before the left child to ensure right-most values are encountered first.

5. Output: The final result is an array (output) containing the values of the rightmost nodes at each level, ordered from top to bottom.

Complexities:

1. Time Complexity: The time complexity of the solution is influenced by the number of nodes in the binary tree. In this solution, the time complexity is O(N), where N is the number of nodes, as all nodes are visited in the tree.

2. Space Complexity: The space complexity is determined by the space required for the queue (nodeQueue) and the set (visitedLevelSet). Again, the space complexity here is O(N), where N is the number of nodes, as all nodes in the tree are queued up to be processed.