Right Side View of Binary Tree in DSA Javascript

Mental Model

We want to see the nodes that are visible when looking at the tree from the right side, which means the rightmost node at each level.

Analogy: Imagine standing on the right side of a tall building with many floors. You only see the windows on the right edge of each floor, not the ones behind or to the left.

      1
     / \
    2   3
     \   \
      5   4

Right side view: 1 -> 3 -> 4

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3; 2 -> null, 5; 3 -> null, 4

Goal: Find the rightmost node at each level to form the right side view list

Step 1: Start at root node 1, add it to queue for level order traversal

Queue: [1]

Why: We begin level by level from the root to find rightmost nodes

Step 2: Process level 0: dequeue 1, enqueue children 2 and 3; record 1 as rightmost at this level

Queue: [2, 3]
Right side view: [1]

Why: Node 1 is the only node at level 0, so it is the rightmost

Step 3: Process level 1: dequeue 2, enqueue child 5; dequeue 3, enqueue child 4; record 3 as rightmost at this level

Queue: [5, 4]
Right side view: [1, 3]

Why: At level 1, nodes are 2 and 3; 3 is the rightmost

Step 4: Process level 2: dequeue 5 (no children), dequeue 4 (no children); record 4 as rightmost at this level

Queue: []
Right side view: [1, 3, 4]

Why: At level 2, nodes are 5 and 4; 4 is the rightmost

Result:

Right side view list: [1, 3, 4]

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function rightSideView(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      // If this is the last node in the current level, add its value
      if (i === levelSize - 1) {
        result.push(node.val);
      }
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}

// Driver code
const root = new TreeNode(1,
  new TreeNode(2, null, new TreeNode(5)),
  new TreeNode(3, null, new TreeNode(4))
);
const view = rightSideView(root);
console.log(view.join(', '));

if (!root) return [];

handle empty tree edge case

const queue = [root];

initialize queue for level order traversal starting at root

const levelSize = queue.length;

determine number of nodes at current level

const node = queue.shift();

remove node from front of queue to process

if (i === levelSize - 1) { result.push(node.val); }

add value of rightmost node at this level to result

if (node.left) queue.push(node.left);

enqueue left child if exists

if (node.right) queue.push(node.right);

enqueue right child if exists

Output

1, 3, 4

Complexity Analysis

Time: O(n) because we visit each node exactly once during the level order traversal

Space: O(n) because in the worst case the queue can hold all nodes at the last level

vs Alternative: Compared to a DFS approach, BFS naturally processes nodes level by level, making it easier to identify rightmost nodes without extra bookkeeping

Edge Cases

Empty tree (root is null)

Returns an empty list since there are no nodes to view

DSA Javascript

if (!root) return [];

Tree with only one node

Returns a list with that single node's value

DSA Javascript

const queue = [root];

Tree where all nodes only have left children

Returns all nodes since each level has only one node which is also the rightmost

DSA Javascript

if (node.left) queue.push(node.left);

When to Use This Pattern

When asked to find nodes visible from one side of a tree, use level order traversal and pick the last node at each level to get the right side view.

Common Mistakes

Mistake: Adding the first node of each level instead of the last node
Fix: Change condition to add node value only when processing the last node in the level (i === levelSize - 1)

Mistake: Using preorder or inorder traversal which does not process nodes level by level
Fix: Use BFS with a queue to process nodes level by level

Summary

Finds the rightmost node at each level of a binary tree to show the right side view.

Use when you need to see the tree as if looking from the right side, level by level.

The key is to do a level order traversal and record the last node visited at each level.

Practice

1. What does the Right Side View of a binary tree represent?

easy

A. The nodes at the deepest level of the tree

B. The nodes visible when the tree is viewed from the right side

C. All leaf nodes of the tree

D. The nodes visible when the tree is viewed from the left side

Solution

1. Step 1: Understand the view perspective

   The right side view shows nodes visible when looking at the tree from the right side.

2. Step 2: Identify visible nodes

   Only the rightmost node at each level is visible from the right side.

3. Final Answer:

   The nodes visible when the tree is viewed from the right side -> Option B

4. Quick Check:

   Right side view = rightmost nodes at each level [OK]

Hint: Right side view shows rightmost nodes at each tree level [OK]

Common Mistakes:

• Confusing right side view with left side view
• Thinking it shows all leaf nodes
• Assuming it shows deepest nodes only

2. Which of the following JavaScript function signatures correctly represents a function to get the right side view of a binary tree?

easy

A. function rightSideView() { }

B. function rightSideView(root, result) { }

C. function rightSideView(root) { }

D. function rightSideView(tree, level) { }

Solution

1. Step 1: Check typical function signature

   The function usually takes the root node as input to start traversal.

2. Step 2: Validate options

   function rightSideView(root) { } correctly takes only the root node, which is standard for this problem.

3. Final Answer:

   function rightSideView(root) { } -> Option C

4. Quick Check:

   Function takes root node only [OK]

Hint: Function usually takes root node as single parameter [OK]

Common Mistakes:

• Adding unnecessary parameters
• Omitting root parameter
• Using unclear parameter names

3. What is the output of the following code snippet for the given binary tree?

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new TreeNode(1,
  new TreeNode(2, null, new TreeNode(5)),
  new TreeNode(3, null, new TreeNode(4))
);

function rightSideView(root) {
  const result = [];
  const queue = [root];
  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (i === size - 1) result.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}

console.log(rightSideView(root));

medium

A. [1, 3, 4]

B. [1, 2, 5]

C. [1, 3, 5]

D. [1, 2, 4]

Solution

1. Step 1: Traverse level by level and identify rightmost nodes

   Level 1: Node 1 (only node), Level 2: Nodes 2 and 3 (rightmost is 3), Level 3: Nodes 5 and 4 (rightmost is 4).

2. Step 2: Collect rightmost nodes in order

   Result array is [1, 3, 4].

3. Final Answer:

   [1, 3, 4] -> Option A

4. Quick Check:

   Rightmost nodes per level = [1, 3, 4] [OK]

Hint: Pick last node at each level during BFS [OK]

Common Mistakes:

• Choosing leftmost nodes instead of rightmost
• Mixing node values from different levels
• Forgetting to check all nodes at a level

4. Identify the bug in the following code that attempts to find the right side view of a binary tree:

function rightSideView(root) {
  const result = [];
  const queue = [root];
  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (i === 0) result.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}

medium

A. It pushes the leftmost node instead of the rightmost node at each level

B. It does not check if root is null

C. It uses shift() which is inefficient

D. It pushes both left and right children in wrong order

Solution

1. Step 1: Analyze the condition for pushing node values

   The code pushes node.val when i === 0, which is the first node at each level (leftmost).

2. Step 2: Understand right side view requirement

   Right side view requires the rightmost node at each level, which is when i === size - 1.

3. Final Answer:

   It pushes the leftmost node instead of the rightmost node at each level -> Option A

4. Quick Check:

   Right side view needs last node per level, not first [OK]

Hint: Push node when i equals size-1 for right side view [OK]

Common Mistakes:

• Using i === 0 instead of i === size - 1
• Ignoring null root check
• Confusing order of child insertion

5. Given a binary tree where some nodes have only left children, how would the right side view look? Example tree:

    1
   /
  2
 / 
3

What is the right side view output for this tree?

hard

A. [3]

B. [1]

C. [1, 3]

D. [1, 2, 3]

Solution

1. Step 1: Visualize the tree and right side view

   Since all nodes are on the left, the right side view shows these nodes as they are the only visible ones.

2. Step 2: List nodes level-wise

   Level 1: 1, Level 2: 2, Level 3: 3. All are visible from right side as no right nodes block view.

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

   Right side view includes all nodes when only left children exist [OK]

Hint: If no right child, left child is visible from right side [OK]

Common Mistakes:

• Assuming right side view is empty if no right children
• Skipping left children in right side view
• Confusing right side view with right subtree nodes only