1/**
2 * Definition for a binary tree node.
3 */
4public class TreeNode {
5     int val;
6     TreeNode left;
7     TreeNode right;
8     TreeNode() {}
9     TreeNode(int val) { this.val = val; }
10     TreeNode(int val, TreeNode left, TreeNode right) {
11         this.val = val;
12         this.left = left;
13         this.right = right;
14     }
15}
16
17class Solution {
18    /**
19     * Finds the lowest common ancestor (LCA) of the deepest leaves in a binary tree.
20     *
21     * @param root the root of the binary tree.
22     * @return the TreeNode representing the LCA of the deepest leaves.
23     */
24    public TreeNode lcaDeepestLeaves(TreeNode root) {
25        return depthFirstSearch(root).getKey();
26    }
27
28    /**
29     * Helper method to perform depth-first search to find the LCA of the deepest leaves.
30     *
31     * @param node the current node under consideration.
32     * @return a Pair containing the current LCA node and the depth of the subtree rooted at the node.
33     */
34    private Pair<TreeNode, Integer> depthFirstSearch(TreeNode node) {
35        if (node == null) {
36            // Base case: if the current node is null, return a pair of (null, 0)
37            return new Pair<>(null, 0);
38        }
39        // Recursively find the depth and LCA in the left subtree
40        Pair<TreeNode, Integer> leftPair = depthFirstSearch(node.left);
41        // Recursively find the depth and LCA in the right subtree
42        Pair<TreeNode, Integer> rightPair = depthFirstSearch(node.right);
43      
44        int leftDepth = leftPair.getValue(), rightDepth = rightPair.getValue();
45      
46        if (leftDepth > rightDepth) {
47            // If the left subtree is deeper, return the LCA and depth of the left subtree
48            return new Pair<>(leftPair.getKey(), leftDepth + 1);
49        }
50        if (leftDepth < rightDepth) {
51            // If the right subtree is deeper, return the LCA and depth of the right subtree
52            return new Pair<>(rightPair.getKey(), rightDepth + 1);
53        }
54        // If both subtrees have the same depth, the current node is the LCA
55        return new Pair<>(node, leftDepth + 1);
56    }
57}
58
59/**
60 * A helper class to store a pair of objects.
61 *
62 * @param <K> the type of the first element.
63 * @param <V> the type of the second element.
64 */
65class Pair<K, V> {
66    private K key;
67    private V value;
68
69    public Pair(K key, V value) {
70        this.key = key;
71        this.value = value;
72    }
73  
74    public K getKey() {
75        return key;
76    }
77  
78    public V getValue() {
79        return value;
80    }
81}
82

1// Definition for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    TreeNode() : val(0), left(nullptr), right(nullptr) {}
7    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
9};
10
11class Solution {
12public:
13    // Function to find the lowest common ancestor of the deepest leaves.
14    TreeNode* lcaDeepestLeaves(TreeNode* root) {
15        return depthFirstSearch(root).first;
16    }
17
18    // Helper function to perform depth-first search.
19    // It will return a pair consisting of the lowest common ancestor at the current subtree and the depth of the deepest leaves.
20    pair<TreeNode*, int> depthFirstSearch(TreeNode* node) {
21        if (!node) {
22            // If the node is null, return a pair of nullptr and depth 0.
23            return {nullptr, 0};
24        }
25      
26        // Recursively look for deepest leaves in the left and right subtrees.
27        auto [leftSubtreeLCA, leftDepth] = depthFirstSearch(node->left);
28        auto [rightSubtreeLCA, rightDepth] = depthFirstSearch(node->right);
29      
30        if (leftDepth > rightDepth) {
31            // If the left subtree is deeper, return the left subtree's LCA and depth.
32            return {leftSubtreeLCA, leftDepth + 1};
33        } else if (leftDepth < rightDepth) {
34            // If the right subtree is deeper, return the right subtree's LCA and depth.
35            return {rightSubtreeLCA, rightDepth + 1};
36        } else {
37            // If both subtrees have the same depth, return the current node as the LCA, as both its left and right subtree have the deepest leaves.
38            return {node, leftDepth + 1};
39        }
40    }
41};
42

1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8        this.val = val === undefined ? 0 : val;
9        this.left = left === undefined ? null : left;
10        this.right = right === undefined ? null : right;
11    }
12}
13
14// Finds the lowest common ancestor of the deepest leaves in a binary tree.
15function lcaDeepestLeaves(root: TreeNode | null): TreeNode | null {
16    // A depth-first search function that returns both the potential lowest common ancestor and the depth.
17    const depthFirstSearch = (node: TreeNode | null): [TreeNode | null, number] => {
18        // If the current node is null, return null and depth 0.
19        if (node === null) {
20            return [null, 0];
21        }
22        // Recursively find the left and right children's deepest nodes and depths.
23        const [leftAncestor, leftDepth] = depthFirstSearch(node.left);
24        const [rightAncestor, rightDepth] = depthFirstSearch(node.right);
25
26        // If the left subtree is deeper, return the left child's ancestor and increase the depth by 1.
27        if (leftDepth > rightDepth) {
28            return [leftAncestor, leftDepth + 1];
29        }
30        // If the right subtree is deeper, return the right child's ancestor and increase the depth by 1.
31        if (leftDepth < rightDepth) {
32            return [rightAncestor, rightDepth + 1];
33        }
34        // If both subtrees have the same depth, the current node is their lowest common ancestor, depth is increased by 1.
35        return [node, leftDepth + 1];
36    };
37
38    // Start the depth-first search from the root and return the lowest common ancestor.
39    return depthFirstSearch(root)[0];
40}
41