Lowest Common Ancestor Node

1. Problem Description

Given a binary tree and two nodes o1 and o2 in the tree, find their lowest common ancestor.

2. Approach

• Similar to Lowest Common Ancestor of a Binary Tree, except here q and p are integer values rather than *TreeNode nodes

1. Approach 1
   • Any two nodes in a tree have a common ancestor; at minimum the root is common to both.
   • If there is a common ancestor, the DFS paths must contain common nodes. Scan backward to find the last common value
2. Approach 2
   • Recursion

3. Implementation

3.1. DFS Paths

// Space: O(N)
// Time: O(N)
func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int {
	if root == nil {
		return 0
	}

	path1 := make([]int, 0)
	path1Flag := findPath(root, o1, &path1)

	path2 := make([]int, 0)
	path2Flag := findPath(root, o2, &path2)

	if !path1Flag || !path2Flag {
		return 0
	}

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

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

	return 0
}

func findPath(root *TreeNode, data int, path *[]int) bool {
	if root == nil {
		return false
	}

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

3.2. Recursion

// Time: O(N)
// Space: O(h), O(N) in the worst case
func lowestCommonAncestor2(root *TreeNode, o1 int, o2 int) int {
	return commonAncestor(root, o1, o2).Val
}

func commonAncestor(root *TreeNode, o1 int, o2 int) *TreeNode {
	if root == nil || root.Val == o1 || root.Val == o2 {
		return root
	}

	left := commonAncestor(root.Left, o1, o2)
	right := commonAncestor(root.Right, o1, o2)

	if left == nil {
		return right
	}
	if right == nil {
		return left
	}

	return root

}

4. References

• Find the Lowest Common Ancestor of Two Nodes in a Binary Tree - NowCoder