Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Tree BFS

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtree-bfs

Binary Tree Right Side View

Problem (restated)

Return the values of nodes visible from the right side (top to bottom).

Intuition

BFS by levels; the last node in each level is the rightmost.

Approaches

Level-order last node

Tested only
Time O(n)Space O(w)

Idea. standard level queue; append level[^1].val each round.

Walkthrough. [1,2,3,null,5,null,4] → [1,3,4].

Trade-offs. DFS with depth map also works; BFS is the tree-bfs template.

Solution
export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

export function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];
  const q: TreeNode[] = [root];
  while (q.length) {
    const size = q.length;
    for (let i = 0; i < size; i++) {
      const n = q.shift()!;
      if (i === size - 1) res.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
  }
  return res;
}

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

export function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];
  const q: TreeNode[] = [root];
  while (q.length) {
    const size = q.length;
    for (let i = 0; i < size; i++) {
      const n = q.shift()!;
      if (i === size - 1) res.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
  }
  return res;
}

Template connection

Tree BFS level answers.

Reflection