Skip to main content
Mapagam

Recognizing Tree Pattern Signals

1. Recognizing Level-Order Traversal Signal

Signal Description Indicates
Processing nodes level by level Nodes are visited from left to right, level by level Tree traversal pattern
Use of queue data structure Nodes are added and removed in FIFO order Level-order traversal implementation
Breadth-First Search (BFS) Exploring all nodes at the current depth before moving to the next Tree or graph traversal
Print by levels Outputting nodes grouped by their depth in the tree Tree visualization or level grouping
Finding maximum width Calculating the widest level in a tree Tree structure analysis

Example: Level-Order Traversal Using Queue

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 also known as breadth-first traversal and is commonly implemented using a queue.

2. Recognizing Path/Subtree Property Signal

Signal Description Common Patterns Examples
Path Sum Sum of values along a path from root to leaf or any node Binary Tree, N-ary Tree Path sum from root to leaf = 22
Subtree Sum Sum of values in a subtree rooted at any node Binary Tree, N-ary Tree Subtree sum at node 5 = 15
Path to Node Sequence of nodes from root to a specific node Binary Tree, N-ary Tree Path to node 7: [1, 2, 5, 7]
Path Length Number of nodes in a path from root to leaf or any node Binary Tree, N-ary Tree Path length from root to node 6 = 3

Example: Path Sum in Binary Tree

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

function hasPathSum(root, targetSum) {
  if (!root) return false;
  if (!root.left && !root.right) return root.val === targetSum;
  return hasPathSum(root.left, targetSum - root.val) ||
         hasPathSum(root.right, targetSum - root.val);
}

// Example usage:
const root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);

console.log(hasPathSum(root, 22)); // true (5 -> 4 -> 11 -> 7)

Example: Subtree Sum in Binary Tree

function subtreeSum(root) {
  if (!root) return 0;
  return root.val + subtreeSum(root.left) + subtreeSum(root.right);
}

// Example usage:
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);

console.log(subtreeSum(root)); // 30 (10 + 5 + 15 + 3 + 7)

3. Recognizing Tree Diameter/Height Signal

Signal Description Indicates
Longest path between any two nodes Maximum distance between leaf nodes in a tree Tree diameter
Maximum depth from root to leaf Longest path from root to any leaf node Tree height

Example: Calculating Tree Diameter

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

function diameterOfBinaryTree(root) {
  let maxDiameter = 0;

  function height(node) {
    if (!node) return 0;
    
    const leftHeight = height(node.left);
    const rightHeight = height(node.right);
    
    maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
    
    return 1 + Math.max(leftHeight, rightHeight);
  }

  height(root);
  return maxDiameter;
}

// 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);

console.log(diameterOfBinaryTree(root)); // Output: 3

Example: Calculating Tree Height

function heightOfBinaryTree(root) {
  if (!root) return 0;
  
  return 1 + Math.max(
    heightOfBinaryTree(root.left),
    heightOfBinaryTree(root.right)
  );
}

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

console.log(heightOfBinaryTree(root)); // Output: 3
Note: The diameter of a binary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

4. Recognizing Lowest Common Ancestor Signal

Signal Description Use Case Common Algorithms
Shared ancestor in tree Two nodes share a common ancestor, and we need to find the deepest such node File system navigation, family tree queries, DOM traversal Binary search on paths, parent tracking, Euler tour

Example: Finding LCA in Binary Tree

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

function findLCA(root, p, q) {
  if (!root || root.val === p || root.val === q) return root;

  const left = findLCA(root.left, p, q);
  const right = findLCA(root.right, p, q);

  if (left && right) return root;
  return left || right;
}

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

const lca = findLCA(root, 5, 1);
console.log(lca.val); // 3
Note: The LCA problem is often solved using recursive traversal or parent pointers. For large trees, consider using binary lifting for O(log n) query time.

Was this article helpful?

Related Cheat Sheets