## Algorithm

Problem Name: 1123. Lowest Common Ancestor of Deepest Leaves

Given the `root` of a binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

• The node of a binary tree is a leaf if and only if it has no children
• The depth of the root of the tree is `0`. if the depth of a node is `d`, the depth of each of its children is `d + 1`.
• The lowest common ancestor of a set `S` of nodes, is the node `A` with the largest depth such that every node in `S` is in the subtree with root `A`.

Example 1:

```Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest leaf-nodes of the tree.
Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.```

Example 2:

```Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree, and it's the lca of itself.
```

Example 3:

```Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.
```

Constraints:

• The number of nodes in the tree will be in the range `[1, 1000]`.
• `0 <= Node.val <= 1000`
• The values of the nodes in the tree are unique.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
return dfs(root).node;
}

private NodeResult dfs(TreeNode root) {
if (root == null) {
return new NodeResult(null, 0);
}
NodeResult leftResult = dfs(root.left);
NodeResult rightResult = dfs(root.right);
if (leftResult.distance > rightResult.distance) {
return new NodeResult(leftResult.node, leftResult.distance + 1);
}
if (leftResult.distance < rightResult.distance) {
return new NodeResult(rightResult.node, rightResult.distance + 1);
}
return new NodeResult(root, rightResult.distance + 1);
}

private static class NodeResult {
TreeNode node;
int distance;

public NodeResult(TreeNode node, int distance) {
this.node = node;
this.distance = distance;
}
}
}
``````
Copy The Code &

Input

cmd
root = [3,5,1,6,2,0,8,null,null,7,4]

Output

cmd
[2,7,4]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
let maxDepth = 0, lcaNode = null

function lca(node, depth) {
if(node == null) return depth - 1
maxDepth = Math.max(depth, maxDepth)
const left = lca(node.left, depth + 1)
const right = lca(node.right, depth + 1)
if(left === maxDepth && right === maxDepth) {
lcaNode = node
}
return Math.max(left, right)
}

lca(root, 0)
return lcaNode
};
``````
Copy The Code &

Input

cmd
root = [3,5,1,6,2,0,8,null,null,7,4]

Output

cmd
[2,7,4]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
def helper(root):
if not root:
return 0, None
d1, lca1 = helper(root.left)
d2, lca2 = helper(root.right)
if d1 > d2:
node = lca1
elif d1 < d2:
node = lca2
else:
node = root
return max(d1, d2) + 1, node
return helper(root)[1]
``````
Copy The Code &

Input

cmd
root = [1]

Output

cmd
[1]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _1123_LowestCommonAncestorOfDeepestLeaves
{
private int maxDepth = 0;
private TreeNode result = null;

{
Helper(root, 0);
return result;
}

public int Helper(TreeNode node, int level)
{
if (node == null)
return 0;

int left = Helper(node.left, level + 1);
int right = Helper(node.right, level + 1);

if (left == right && level + left >= maxDepth)
{
maxDepth = level + left;
result = node;
}

return Math.Max(left, right) + 1;
}
}
}
``````
Copy The Code &

Input

cmd
root = [1]

Output

cmd
[1]