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

Tree DFS

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Tree BFS →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 5
351620874

p = 5 · q = 1

LCA of 5 and 1. Search the tree structure: each call returns whether p/q found in a subtree.

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

Mediumtree-dfs

Lowest Common Ancestor of a Binary Tree

Problem (restated)

Given a binary tree and two nodes p and q, return their lowest common ancestor (deepest node that has both as descendants).

Intuition

If left finds one and right finds the other, this node is LCA. If both under one side, return that side.

Approaches

Post-order LCA

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

Idea. dfs: if node is p or q or null return node; combine left/right results.

Walkthrough. p and q on different sides of root → root is LCA.

Trade-offs. Recursive post-order is standard; parent pointers need extra structure.

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 lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null,
): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}

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 lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null,
): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}

Template connection

Tree DFS return subtree witness.

Reflection