Skip to main content
Mapagam

Implementing Tree Breadth-First Search

1. Understanding Level Order Traversal

Level order traversal (also known as breadth-first search or BFS) processes nodes of a tree level by level, from left to right.

Property Description Usage
Queue Used to store nodes at each level during traversal Enqueue children of current node before dequeuing next node
Level Represents the depth of the current node in the tree Used to group nodes by their level for processing

Example: Basic Level Order Traversal

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

function levelOrder(root) {
  if (!root) return [];
  
  const result = [];
  const queue = [root];
  
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.val);
    
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  
  return result;
}

// Example usage:
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(levelOrder(root)); // [3, 9, 20, 15, 7]
Note: Level order traversal is particularly useful for problems that require processing nodes by their depth or level, such as finding the maximum depth of a tree or printing nodes at each level.

2. Implementing Basic BFS

Example: Basic BFS Implementation

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

function bfs(root) {
  if (!root) return [];

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

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.val);

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

  return result;
}

// Example usage:
const root = new TreeNode(1, 
  new TreeNode(2, new TreeNode(4), new TreeNode(5)), 
  new TreeNode(3)
);

console.log(bfs(root)); // [1, 2, 3, 4, 5]
Property Description Usage
queue Used to store nodes to be visited in order Starts with root node, adds children as they are processed
result Stores the traversal order of node values Accumulates values as nodes are visited
shift() Removes and returns the first element from queue Ensures breadth-first order by processing nodes in FIFO manner

3. Traversing Reverse Level Order

Reverse level order traversal (also known as bottom-up level order traversal) visits nodes from the deepest level to the shallowest, processing each level from left to right.

Operation Description Implementation
Reverse Level Order Traverses tree levels from bottom to top, left to right. 
function reverseLevelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    result.unshift(node.val);
    if (node.right) queue.push(node.right);
    if (node.left) queue.push(node.left);
  }

  return result;
}

Example: Reverse Level Order Traversal

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

const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

console.log(reverseLevelOrder(root)); // [7, 15, 20, 9, 3]
Note: The traversal uses a queue to process nodes level by level, and prepends each node's value to the result array to achieve reverse order.

4. Traversing Zigzag Level Order

Property Description Example
zigzagLevelOrder Traverses tree nodes in zigzag level order, alternating direction per level 
function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [];
  let queue = [root];
  let leftToRight = true;

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);

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

    if (!leftToRight) {
      currentLevel.reverse();
    }
    result.push(currentLevel);
    leftToRight = !leftToRight;
  }

  return result;
}

Example: Zigzag Traversal

const root = {
  val: 3,
  left: { val: 9 },
  right: { 
    val: 20,
    left: { val: 15 },
    right: { val: 7 }
  }
};

console.log(zigzagLevelOrder(root)); 
// Output: [[3], [20, 9], [15, 7]]

5. Finding Level Averages

Property Description Example
levelAverages Function to calculate the average value of nodes at each level in a binary tree levelAverages(root)

Example: Finding Level Averages

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

function levelAverages(root) {
  if (!root) return [];

  const averages = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    let levelSum = 0;

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      levelSum += node.val;

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

    averages.push(levelSum / levelSize);
  }

  return averages;
}

// Example usage:
const root = new TreeNode(3, 
  new TreeNode(9), 
  new TreeNode(20, new TreeNode(15), new TreeNode(7))
);

console.log(levelAverages(root)); // [3, 14.5]
Note: The function returns an array of averages, one for each level in the tree.

6. Finding Level Minimum

Property Description Example
levelMin(node, targetLevel) Finds the minimum value in a specific level of the tree levelMin(root, 2); // Returns minimum value at level 2

Example: Finding Minimum in Level 2

function levelMin(node, targetLevel) {
  if (!node || targetLevel < 0) return Infinity;
  if (targetLevel === 0) return node.value;

  let min = Infinity;
  const queue = [[node, 0]];

  while (queue.length > 0) {
    const [currentNode, level] = queue.shift();
    
    if (level === targetLevel) {
      min = Math.min(min, currentNode.value);
    } else if (level < targetLevel) {
      if (currentNode.left) queue.push([currentNode.left, level + 1]);
      if (currentNode.right) queue.push([currentNode.right, level + 1]);
    }
  }

  return min === Infinity ? null : min;
}

7. Finding Level Maximum

Property Description Example
levelMax Maximum value in a specific level of the tree 
const levelMax = (root, level) => {
  if (!root) return null;
  const queue = [{ node: root, depth: 0 }];
  let max = -Infinity;

  while (queue.length > 0) {
    const { node, depth } = queue.shift();
    if (depth === level) {
      max = Math.max(max, node.val);
    } else if (depth < level) {
      if (node.left) queue.push({ node: node.left, depth: depth + 1 });
      if (node.right) queue.push({ node: node.right, depth: depth + 1 });
    }
  }

  return max;
};

Example: Finding Maximum in Level 2

const root = {
  val: 1,
  left: { val: 2, left: { val: 4 }, right: { val: 5 } },
  right: { val: 3, left: { val: 6 }, right: { val: 7 } }
};

console.log(levelMax(root, 2)); // Output: 7

8. Implementing Level Order Successor

Property Description Example
levelOrderSuccessor Function to find the next node in level order traversal after a given node levelOrderSuccessor(root, targetNode)

Example: Finding Level Order Successor

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

function levelOrderSuccessor(root, targetNode) {
  if (!root || !targetNode) return null;

  const queue = [root];
  let found = false;

  while (queue.length > 0) {
    const current = queue.shift();

    if (found && current) {
      return current;
    }

    if (current === targetNode) {
      found = true;
    }

    if (current?.left) queue.push(current.left);
    if (current?.right) queue.push(current.right);
  }

  return null;
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

const successor = levelOrderSuccessor(root, root.left);
console.log(successor.val); // Output: 3
Note: The successor is determined by level order traversal (BFS), and the function returns null if no successor exists.

9. Connecting Level Order Siblings

Property Description Usage
node.next Pointer to the next node at the same level Used to link nodes in level order

Example: Connecting Level Order Siblings

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

function connectLevelOrderSiblings(root) {
  if (!root) return null;

  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    let prev = null;

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();

      if (prev) {
        prev.next = node;
      }
      prev = node;

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

  return root;
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

connectLevelOrderSiblings(root);

// Now, each node's next pointer connects to the next node at the same level

10. Finding Right Side View

Property Description Example
rightSideView Function to return the rightmost node values at each level of a binary tree function rightSideView(root) { ... }

Example: Right Side View of Binary Tree

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

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(5);

// Right side view: [1, 3, 5]
console.log(rightSideView(root)); // [1, 3, 5]
Note: The right side view is determined by traversing the tree level-by-level and selecting the last node at each level.

11. Finding Boundary Traversal

Property Description Example
Boundary Nodes Nodes on the left and right boundaries of a tree, including leaves [1, 2, 4, 5, 6, 7]
Left Boundary Nodes from root to leftmost leaf, including root and leaves [1, 2, 4]
Right Boundary Nodes from root to rightmost leaf, excluding root and leaves [1, 3, 7]

Example: Boundary Traversal

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

function boundaryOfBinaryTree(root) {
  if (!root) return [];

  const result = [root.val];
  const leftBoundary = [];
  const leaves = [];
  const rightBoundary = [];

  function getLeftBoundary(node) {
    if (!node || (!node.left && !node.right)) return;
    leftBoundary.push(node.val);
    if (node.left) {
      getLeftBoundary(node.left);
    } else {
      getLeftBoundary(node.right);
    }
  }

  function getRightBoundary(node) {
    if (!node || (!node.left && !node.right)) return;
    rightBoundary.push(node.val);
    if (node.right) {
      getRightBoundary(node.right);
    } else {
      getRightBoundary(node.left);
    }
  }

  function collectLeaves(node) {
    if (!node) return;
    if (!node.left && !node.right) {
      leaves.push(node.val);
    }
    collectLeaves(node.left);
    collectLeaves(node.right);
  }

  if (root.left) {
    getLeftBoundary(root.left);
  }
  collectLeaves(root);
  if (root.right) {
    getRightBoundary(root.right);
  }

  return [
    ...result,
    ...leftBoundary,
    ...leaves.slice(1),
    ...rightBoundary.reverse()
  ];
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

console.log(boundaryOfBinaryTree(root)); // [1, 2, 4, 5, 6, 7]
Note: The boundary traversal includes the root, left boundary (excluding leaves), all leaves, and right boundary in reverse order (excluding leaves).

12. Checking Tree Symmetry Property

Property Description Implementation
Symmetric Tree A tree is symmetric if it is a mirror of itself. 
function isSymmetric(root) {
  function isMirror(left, right) {
    if (!left && !right) return true;
    if (!left || !right) return false;
    return (left.val === right.val) && isMirror(left.left, right.right) && isMirror(left.right, right.left);
  }
  return isMirror(root.left, root.right);
}

Example: Symmetric Tree Check

const root = {
  val: 1,
  left: { val: 2, left: { val: 3 }, right: { val: 4 } },
  right: { val: 2, left: { val: 4 }, right: { val: 3 } }
};

console.log(isSymmetric(root)); // true
Note: The symmetry check uses recursive comparison of left and right subtrees to ensure mirrored structure.

Was this article helpful?

Related Cheat Sheets