Section 4: Trees and Graphs

1. Binary Tree Inorder Traversal (Recursive & Iterative)

JavaScript:

function inorderTraversal(root) {
  const res = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.left);
    res.push(node.val);
    dfs(node.right);
  }
  dfs(root);
  return res;
}

function inorderTraversalIterative(root) {
  const res = [], stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    res.push(curr.val);
    curr = curr.right;
  }
  return res;
}

Explanation:

• Inorder traversal (Left → Node → Right) is used to get sorted order in BSTs.

• Recursive approach uses depth-first traversal and implicit call stack.

• Iterative approach manually simulates recursion using an explicit stack.

Time Complexity: O(n)
Space Complexity: O(h) (call stack or explicit stack, where h = height of the tree)

2. Maximum Depth of Binary Tree

JavaScript:

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

Explanation:

• This is a basic DFS problem.

• At each node, we recursively compute the maximum depth of the left and right subtrees, and add 1.

• Useful to understand recursive tree traversal and base case design.

Time Complexity: O(n)
Space Complexity: O(h)

3. Invert Binary Tree

JavaScript:

function invertTree(root) {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

Explanation:

• Recursively swap left and right child of every node.

• Helps develop intuition about structural transformations on trees.

Time Complexity: O(n)
Space Complexity: O(h)

4. Diameter of Binary Tree

JavaScript:

function diameterOfBinaryTree(root) {
  let diameter = 0;
  function dfs(node) {
    if (!node) return 0;
    let left = dfs(node.left);
    let right = dfs(node.right);
    diameter = Math.max(diameter, left + right);
    return 1 + Math.max(left, right);
  }
  dfs(root);
  return diameter;
}

Explanation:

• Diameter is the length of the longest path between any two nodes in the tree.

• At each node, compute max depth of left and right subtrees, sum them, and update global maximum.

Time Complexity: O(n)
Space Complexity: O(h)

5. Same Tree Check

JavaScript:

function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q || p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Explanation:

• Recursively compare structure and node values.

• A common question to test recursive thinking and base case design.

Time Complexity: O(n)
Space Complexity: O(h)

6. Lowest Common Ancestor (LCA)

JavaScript:

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  return !left ? right : !right ? left : root;
}

Explanation:

• LCA is the deepest node that has both p and q as descendants.

• Use post-order DFS. If p and q are found in different subtrees, current node is the LCA.

Time Complexity: O(n)
Space Complexity: O(h)

7. Level Order Traversal (BFS)

JavaScript:

function levelOrder(root) {
  const res = [], queue = [];
  if (root) queue.push(root);
  while (queue.length) {
    const level = [], n = queue.length;
    for (let i = 0; i < n; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(level);
  }
  return res;
}

Explanation:

• Breadth-first search to traverse level by level.

• Use a queue to store nodes of current level.

Time Complexity: O(n)
Space Complexity: O(n)

8. Right Side View of Binary Tree

JavaScript:

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

Explanation:

• Track the last node of each level in level-order traversal.

• That last node is what you see from the right.

Time Complexity: O(n)
Space Complexity: O(n)

9. Detect Cycle in Undirected Graph (Union Find)

JavaScript:

function hasCycle(edges, n) {
  const parent = Array(n).fill(0).map((_, i) => i);
  
  function find(x) {
    if (x !== parent[x]) parent[x] = find(parent[x]);
    return parent[x];
  }
  
  function union(x, y) {
    const rootX = find(x), rootY = find(y);
    if (rootX === rootY) return false;
    parent[rootX] = rootY;
    return true;
  }

  for (const [u, v] of edges) {
    if (!union(u, v)) return true;
  }
  return false;
}

Explanation:

• Use Union-Find (Disjoint Set Union) to detect if adding an edge connects two nodes already in the same set.

• If yes, it forms a cycle.

Time Complexity: O(E * α(N)) where α is inverse Ackermann.
Space Complexity: O(N)

10. Topological Sort (Kahn's Algorithm)

JavaScript:

function topologicalSort(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indegree = Array(numCourses).fill(0);

  for (let [u, v] of prerequisites) {
    graph[v].push(u);
    indegree[u]++;
  }

  const queue = [], res = [];
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  while (queue.length) {
    const node = queue.shift();
    res.push(node);
    for (let nei of graph[node]) {
      indegree[nei]--;
      if (indegree[nei] === 0) queue.push(nei);
    }
  }

  return res.length === numCourses ? res : [];
}

Explanation:

• Topological sort orders nodes in a Directed Acyclic Graph (DAG) such that for any edge (u → v), u appears before v.

• Kahn’s algorithm repeatedly removes nodes with zero indegree and updates their neighbors.

Time Complexity: O(V + E)
Space Complexity: O(V + E)