Lowest Common Ancestor in Binary Tree in DSA C#

Mental Model

Find the closest shared parent node of two given nodes in a tree by checking where their paths meet first.

Analogy: Imagine two friends walking up a family tree to find their closest common grandparent where their paths cross.

       3
      / \
     5   1
    / \ / \
   6  2 0  8
     / \
    7   4

Nodes: 5 and 1
Goal: Find their lowest common ancestor

Dry Run Walkthrough

Input: Binary tree with nodes 3,5,1,6,2,0,8,7,4; find LCA of nodes 5 and 1

Goal: Find the lowest common ancestor node of 5 and 1

Step 1: Start at root node 3, check if it matches 5 or 1

3 ↑
/ \
5  1
...

Why: We start from the root to find where both nodes appear in the tree

Step 2: Recursively search left subtree of 3 for nodes 5 and 1

5 ↑
/ \
6  2
...

Why: Check if left subtree contains either node

Step 3: Find node 5 matches current node, return 5

5 ↑
/ \
6  2
...

Why: Found one target node, return it up the call stack

Step 4: Recursively search right subtree of 3 for nodes 5 and 1

1 ↑
/ \
0  8

Why: Check if right subtree contains either node

Step 5: Find node 1 matches current node, return 1

1 ↑
/ \
0  8

Why: Found the other target node, return it up the call stack

Step 6: At node 3, left subtree returned 5, right subtree returned 1, so 3 is LCA

3 ↑
/ \
5  1
...

Why: Both nodes found in different subtrees, so current node is their lowest common ancestor

Result:

3 -> null
Lowest Common Ancestor is node 3

Annotated Code

DSA C#

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null; // base case: empty subtree
        if (root == p || root == q) return root; // found one target node

        TreeNode left = LowestCommonAncestor(root.left, p, q); // search left subtree
        TreeNode right = LowestCommonAncestor(root.right, p, q); // search right subtree

        if (left != null && right != null) return root; // both nodes found in different subtrees
        return left != null ? left : right; // return non-null child or null
    }
}

public class Program {
    public static void Main() {
        TreeNode root = new TreeNode(3,
            new TreeNode(5,
                new TreeNode(6),
                new TreeNode(2,
                    new TreeNode(7),
                    new TreeNode(4)
                )
            ),
            new TreeNode(1,
                new TreeNode(0),
                new TreeNode(8)
            )
        );

        TreeNode p = root.left; // node 5
        TreeNode q = root.right; // node 1

        Solution sol = new Solution();
        TreeNode lca = sol.LowestCommonAncestor(root, p, q);
        Console.WriteLine(lca.val);
    }
}

if (root == null) return null;

stop if subtree is empty

if (root == p || root == q) return root;

return node if it matches one target

TreeNode left = LowestCommonAncestor(root.left, p, q);

search left subtree for targets

TreeNode right = LowestCommonAncestor(root.right, p, q);

search right subtree for targets

if (left != null && right != null) return root;

if both sides found targets, current node is LCA

return left != null ? left : right;

return whichever subtree found a target or null

Output

3

Complexity Analysis

Time: O(n) because we visit each node once in the worst case

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to storing paths and comparing them, this method uses less space and is simpler

Edge Cases

One or both nodes not present in tree

Returns null or the node found if only one is present

DSA C#

if (root == null) return null;

Both nodes are the same node

Returns that node immediately

DSA C#

if (root == p || root == q) return root;

Tree with only root node

Returns root if it matches p or q, else null

DSA C#

if (root == null) return null;

When to Use This Pattern

When asked to find the closest shared ancestor of two nodes in a tree, use recursive subtree search to find where their paths meet first.

Common Mistakes

Mistake: Returning root immediately without checking both subtrees
Fix: Check both left and right subtrees before deciding if current node is LCA

Mistake: Not handling the case when one node is ancestor of the other
Fix: Return node immediately if it matches p or q to handle ancestor cases

Summary

Finds the lowest common ancestor node of two given nodes in a binary tree.

Use when you need to find the closest shared parent of two nodes in a tree structure.

The key insight is that if one node is found in the left subtree and the other in the right, the current node is their lowest common ancestor.

Practice

1. What is the Lowest Common Ancestor (LCA) of two nodes in a binary tree?

easy

A. The node that is a child of both nodes

B. The root node of the binary tree

C. The node with the smallest value between the two nodes

D. The deepest node that is an ancestor of both nodes

Solution

1. Step 1: Understand the definition of LCA

   The Lowest Common Ancestor is the deepest node in the tree that has both given nodes as descendants (a node can be a descendant of itself).

2. Step 2: Identify the correct description

   Among the options, only the deepest common ancestor fits this definition.

3. Final Answer:

   The deepest node that is an ancestor of both nodes -> Option D

4. Quick Check:

   LCA = deepest common ancestor [OK]

Hint: LCA is the lowest node common to both paths [OK]

Common Mistakes:

• Confusing LCA with root node
• Thinking LCA is the smaller value node
• Assuming LCA is a child of both nodes

2. Which of the following is the correct C# method signature to find the LCA in a binary tree node class named TreeNode?

easy

A. public TreeNode FindLCA(TreeNode root, TreeNode p, TreeNode q)

B. public void FindLCA(TreeNode root, int p, int q)

C. private int FindLCA(int root, int p, int q)

D. public TreeNode FindLCA(int root, TreeNode p, TreeNode q)

Solution

1. Step 1: Analyze method parameters and return type

   The method should accept the root node and two nodes to find LCA for, and return a TreeNode representing the LCA.

2. Step 2: Match signature with correct types

   public TreeNode FindLCA(TreeNode root, TreeNode p, TreeNode q) correctly uses TreeNode for all nodes and returns TreeNode. Other options have incorrect parameter types or return types.

3. Final Answer:

   public TreeNode FindLCA(TreeNode root, TreeNode p, TreeNode q) -> Option A

4. Quick Check:

   Correct signature uses TreeNode parameters and return type [OK]

Hint: LCA method returns TreeNode and takes TreeNode parameters [OK]

Common Mistakes:

• Using int instead of TreeNode for nodes
• Wrong return type (void or int)
• Incorrect access modifier or parameter order

3. Given the following binary tree and code snippet, what will be the output of FindLCA(root, node5, node1).val?

    3
   / \
  5   1
 / \ / \
6  2 0  8
   / \
  7   4

// Code snippet:
TreeNode lca = FindLCA(root, node5, node1);
Console.WriteLine(lca.val);

medium

A. 5

B. 3

C. 1

D. 2

Solution

1. Step 1: Locate nodes 5 and 1 in the tree

   Node 5 is left child of root 3, node 1 is right child of root 3.

2. Step 2: Find lowest common ancestor

   The root node 3 is the lowest node that has both 5 and 1 as descendants.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   LCA(5,1) = 3 [OK]

Hint: LCA of nodes on different sides is their root ancestor [OK]

Common Mistakes:

• Choosing one of the nodes instead of their ancestor
• Confusing node values with LCA
• Ignoring tree structure

4. Identify the bug in this C# method to find LCA in a binary tree:

public TreeNode FindLCA(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (root == p || root == q) return root;
    TreeNode left = FindLCA(root.left, p, q);
    TreeNode right = FindLCA(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

medium

A. Missing base case for leaf nodes

B. Should check if root.val equals p.val or q.val instead of node references

C. No bug, method is correct

D. Return statement should always return root

Solution

1. Step 1: Review base cases and recursive calls

   The method returns null if root is null, returns root if root matches p or q, then recursively searches left and right subtrees.

2. Step 2: Check logic for combining results

   If both left and right are non-null, root is LCA; else returns whichever subtree found a node. This is correct logic.

3. Final Answer:

   No bug, method is correct -> Option C

4. Quick Check:

   Standard LCA recursive method is correct [OK]

Hint: Check if both sides return non-null to find LCA [OK]

Common Mistakes:

• Comparing node values instead of references if nodes are unique
• Missing base case for null root
• Incorrect return logic

5. You have a binary tree where nodes may not be unique. How would you modify the LCA method to find the LCA of two nodes given only their values (int pVal, int qVal), assuming multiple nodes can have the same value?

hard

A. Use a method that finds paths from root to each node value and then compare paths to find LCA

B. Modify the method to return the first node found with matching value and use parent pointers to find LCA

C. Return the root node always since values are not unique

D. Use a hash set to store visited nodes and return the first common node visited

Solution

1. Step 1: Understand the problem with non-unique values

   Since values are not unique, we cannot rely on node references or values alone to find LCA directly.

2. Step 2: Use path comparison approach

   Find paths from root to each node value (may find multiple nodes), then compare paths to find the last common node, which is the LCA.

3. Final Answer:

   Use a method that finds paths from root to each node value and then compare paths to find LCA -> Option A

4. Quick Check:

   Path comparison works for non-unique values [OK]

Hint: Find paths for both values, then compare to find LCA [OK]

Common Mistakes:

• Assuming node references are unique
• Returning root always
• Using hash set without paths