Lowest Common Ancestor of a Binary Tree

1. Problem Description

Given a binary tree, find the lowest common ancestor of two specified nodes in the tree.

The lowest common ancestor of two nodes p and q in a rooted tree is a node x such that x is an ancestor of both p and q and has the greatest possible depth. A node may also be an ancestor of itself.

2. Approach

1. Approach 1
   • Use DFS to find the path containing each target node, then scan backward to find the last common node
2. Approach 2
   1. Recursion

3. Implementation

3.1. DFS

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	path1 := make([]*TreeNode, 0)
	if flag := lowestCommonAncestorDFS(root, p, &path1); !flag {
		return nil
	}

	path2 := make([]*TreeNode, 0)
	if flag := lowestCommonAncestorDFS(root, q, &path2); !flag {
		return nil
	}

	if len(path1) > len(path2) {
		path1 = path1[:len(path2)]
	} else {
		path2 = path2[:len(path1)]
	}

	for i := len(path1) - 1; i >= 0; i-- {
		if path1[i] == path2[i] {
			return path1[i]
		}
	}

	return nil
}

func lowestCommonAncestorDFS(root *TreeNode, find *TreeNode, path *[]*TreeNode) bool {
	if root == nil {
		return false
	}

	*path = append(*path, root)
	if root == find {
		return true
	}
	if flag := lowestCommonAncestorDFS(root.Left, find, path); flag {
		return true
	}
	if flag := lowestCommonAncestorDFS(root.Right, find, path); flag {
		return true
	}
	*path = (*path)[:len(*path)-1]
	return false
}

3.2. Recursion

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return root
    }

    if root == p || root == q {
        return root
    }

    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }else if left == nil {
        return right
    }else if right == nil {
        return left
    }
    return nil
}

4. References

• 236. Lowest Common Ancestor of a Binary Tree - LeetCode
• 236. Lowest Common Ancestor of a Binary Tree: DFS - LeetCode
• Classic Recursive Solution - LeetCode