Patterns

Process tree level by level using a queue

When to useLevel traversal, right side view, level-aware computations

iterative

Binary Tree Distance K from Target Node

binary_tree_distance_k_nodes

Binary Tree Level Order Traversal

binary_tree_level_order_traversal

Binary Tree Min Depth

binary_tree_min_depth

Binary Tree Right Side View

binary_tree_right_side_view

Binary Tree ZigZag Level Order Traversal

binary_tree_zig_zag_traversal

Breadth First Search on Trees

bfs_intro

INITIALIZE

queue = [root]; result = []

—

if (root === null) return [];
const result = [];
const queue = [root];
let head = 0;

const queue = [root];
let depth = 0;

const result = [];
const queue = [root];

const result = [];
const queue = [root];
let leftToRight = true;

const result = [];
const queue = [root];

TRAVERSE

while (queue.length)

while (queue.length > 0 && distance < k) {

while (head < queue.length) {

while (queue.length > 0) {

while (queue.length > 0) {

while (queue.length > 0) {

while (queue.length > 0) {

snapshot level

const size = queue.length

—

  const size = queue.length - head;
  const level = [];

  const size = queue.length;

  const size = queue.length;

  const size = queue.length;

—

[PROCESS]

iterate size nodes; collect/process per level

  const next = [];
  for (const node of queue) {
    for (const neighbor of [node.left, node.right, parents.get(node)]) {
      if (neighbor !== null && neighbor !== undefined && !visited.has(neighbor)) {
        visited.add(neighbor);
        next.push(neighbor);
      }
    }
  }
  queue = next;
  distance += 1;

  for (let i = 0; i < size; i++) {
    const node = queue[head];
    head++;
    level.push(node.val);
    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);
  }

  for (let i = 0; i < size; i++) {
    const node = queue.shift();
    if (node.left === null && node.right === null) return depth;
  }

  for (let i = 0; i < size; i++) {
    const node = queue.shift();
    if (i === size - 1) result.push(node.val);
  }

  const level = [];
  for (let i = 0; i < size; i++) {
    const node = queue.shift();
    if (leftToRight) level.push(node.val);
    else level.unshift(node.val);
  }
  result.push(level);
  leftToRight = !leftToRight;

  result.push(node.val);

enqueue children

push node.left and node.right if present

—

    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);

    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);

    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);

  for (const child of node.children ?? []) {
    queue.push(child);
  }

RETURN

return level-aware result

return queue.map((node) => node.val).sort((a, b) => a - b);

return result;

return depth;

return result;

return result;

return result;