# Lowest Common Ancestor of a Binary Tree IV

Medium

Given the `root` of a binary tree and an array of `TreeNode` objects `nodes`, return the lowest common ancestor (LCA) of all the nodes in `nodes`. All the nodes will exist in the tree, and all values of the tree’s nodes are unique.

Extending the definition of LCA on Wikipedia: “The lowest common ancestor of `n` nodes `p1``p2`, …, `pn` in a binary tree `T` is the lowest node that has every `pi` as a descendant (where we allow a node to be a descendant of itself) for every valid `i`“. A descendant of a node `x` is a node `y` that is on the path from node `x` to some leaf node.

Example 1: Binary Tree
``````Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [7,6,2,4]
Output: 5
Explanation: The lowest common ancestor of the nodes 7, 6, 2, and 4 is node 5.
``````

Example 2:

``````Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [0,1,2,3,4,5,6,7,8]
Output: 3
Explanation: The lowest common ancestor of all the nodes is the root node.``````

Implementation

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {

TreeNode lca = null;

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
Set<Integer> targetNodes = new HashSet<>();
for(TreeNode node : nodes) {
targetNodes.add(node.val);
}
DFS(root, targetNodes);
return lca;
}

private int DFS(TreeNode root, Set<Integer> nodes) {
if(root == null) return 0;
int leftCount = DFS(root.left, nodes);
int rightCount = DFS(root.right, nodes);
int foundCount = leftCount + rightCount;

if(nodes.contains(root.val)) {
foundCount++;
}

if(foundCount == nodes.size() && lca == null) {
lca = root;
}

return foundCount;
}
}
```

Categories: Binary Tree, Data Structure

Tagged as: