Problem Explanation

Given a binary tree, we are to find the node whose subtree contains all the deepest nodes. The depth of a node is calculated by the shortest distance to the root node of the tree. The deepest node(s) will be the one(s) with maximum depth.

For example, consider a binary tree serialized as [3,5,1,6,2,0,8,null,null,7,4]. The subtree rooted at node 2 contains all the deepest nodes (7,4) with maximum depth. Therefore, our output would be [2,7,4].

Solution Approach

A depth first search (DFS) approach would be suitable for the problem. For each node in the tree, we recursively calculate the depth of its left and right child nodes. The subtree with the deepest nodes would be one of the following:

1. The left child node, if the depth of the left subtree is greater than the depth of the right subtree.
2. The right child node, if the depth of the right subtree is greater than the left.
3. The current node itself, if both the left and right subtrees have the same depth. In this case, the current node is the lowest common ancestor (LCA) of all the deepest nodes.

We define a struct (or class in Python) to store the LCA node and its corresponding depth. This allows us to easily access and compare the depth of different subtrees and return the corresponding LCA node.

Python Solution

1
2python
3class TreeNodeDepth:
4    def __init__(self, node=None, depth=0):
5        self.node = node
6        self.depth = depth
7
8class Solution:
9    def subtreeWithAllDeepest(self, root):
10        def dfs(node):
11            if not node:
12                return TreeNodeDepth(None, 0)
13            left, right = dfs(node.left), dfs(node.right)
14            if left.depth > right.depth:
15                return TreeNodeDepth(left.node, left.depth + 1)
16            elif left.depth < right.depth:
17                return TreeNodeDepth(right.node, right.depth + 1)
18            else:
19                return TreeNodeDepth(node, left.depth + 1)
20
21        return dfs(root).node

Java Solution

1
2java
3class Solution {
4    private class Result {
5        TreeNode node;
6        int dist;
7        Result(TreeNode n, int d) {
8            node = n;
9            dist = d;
10        }
11    }
12
13    public TreeNode subtreeWithAllDeepest(TreeNode root) {
14        return dfs(root).node;
15    }
16
17    private Result dfs(TreeNode node) {
18        if (node == null) return new Result(null, 0);
19        Result left = dfs(node.left), right = dfs(node.right);
20        if (left.dist > right.dist) return new Result(left.node, left.dist + 1);
21        if (left.dist < right.dist) return new Result(right.node, right.dist + 1);
22        return new Result(node, left.dist + 1);
23    }
24}

JavaScript Solution

1
2javascript
3var subtreeWithAllDeepest = function(root) {
4    function dfs(node) {
5        if (!node) return {node: null, depth: 0};
6        let left = dfs(node.left), right = dfs(node.right);
7        if (left.depth > right.depth) return {node: left.node, depth: left.depth + 1};
8        if (left.depth < right.depth) return {node: right.node, depth: right.depth + 1};
9        return {node: node, depth: left.depth + 1};
10    }
11    return dfs(root).node;
12};

C++ Solution

1
2c++
3class Solution {
4public:
5    struct TreeNodeDepth {
6        TreeNode* node;
7        int depth;
8        TreeNodeDepth() : node(nullptr), depth(0) {}
9        TreeNodeDepth(TreeNode* node, int depth) : node(node), depth(depth) {}
10    };
11  
12    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
13        return dfs(root).node;
14    }
15  
16    TreeNodeDepth dfs(TreeNode* node) {
17        if (!node) return TreeNodeDepth();
18        TreeNodeDepth left = dfs(node->left), right = dfs(node->right);
19        if (left.depth > right.depth) return TreeNodeDepth(left.node, left.depth + 1);
20        if (left.depth < right.depth) return TreeNodeDepth(right.node, right.depth + 1);
21        return TreeNodeDepth(node, left.depth + 1);
22    }
23};

C# Solution

1
2c#
3public class Solution {
4    private (TreeNode node, int depth) Dfs(TreeNode node) {
5        if (node == null) return (node: null, depth: 0);
6        var (lnode, ldepth) = Dfs(node.left);
7        var (rnode, rdepth) = Dfs(node.right);
8        if (ldepth > rdepth) return (node: lnode, depth: ldepth + 1);
9        if (ldepth < rdepth) return (node: rnode, depth: rdepth + 1);
10        return (node: node, depth: ldepth + 1);
11    }
12  
13    public TreeNode SubtreeWithAllDeepest(TreeNode root) {
14        return Dfs(root).node;
15    }
16}

Go Solution

1
2go
3type TreeNodeDepth struct {
4    node *TreeNode
5    depth int
6}
7
8func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
9    result := dfs(root)
10    return result.node
11}
12
13func dfs(node *TreeNode) TreeNodeDepth {
14    if node == nil {
15        return TreeNodeDepth{node: nil, depth: 0}
16    }
17    left := dfs(node.Left)
18    right := dfs(node.Right)
19    if left.depth > right.depth {
20        return TreeNodeDepth{node: left.node, depth: left.depth + 1}
21    }
22    if left.depth < right.depth {
23        return TreeNodeDepth{node: right.node, depth: right.depth + 1}
24    }
25    return TreeNodeDepth{node: node, depth: left.depth + 1}
26}

Rust Solution

1
2rust
3use std::cmp::Ordering;
4
5struct TreeNodeDepth<'a> {
6    node: Option<&'a TreeNode>,
7    depth: i32,
8}
9
10impl Solution {
11    pub fn subtree_with_all_deepest(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
12        let TreeNodeDepth { node, .. } = Solution::dfs(root.as_ref());
13        node.cloned()
14    }
15
16    fn dfs(node: Option<&Rc<RefCell<TreeNode>>>) -> TreeNodeDepth {
17        match node {
18            None => TreeNodeDepth { node, depth: 0 },
19            Some(n) => {
20                let n = n.borrow();
21                let left = Solution::dfs(n.left.as_ref());
22                let right = Solution::dfs(n.right.as_ref());
23                match left.depth.cmp(&right.depth) {
24                    Ordering::Greater => TreeNodeDepth{ node: left.node, depth: left.depth + 1 },
25                    Ordering::Less => TreeNodeDepth{ node: right.node, depth: right.depth + 1 },
26                    Ordering::Equal => TreeNodeDepth{ node: Some(node.unwrap()), depth: left.depth + 1 },
27                }
28            }
29        }
30    }
31}

In this article, we discussed the problem of finding the subtree that includes all the deepest nodes in a binary tree. It is a pretty standard problem involving depth-first search in a binary tree, but the challenge lies in the implementation details in different languages. The solution approach remains the same across Python, JS, Java, Go, C#, C++, and Rust: perform a depth-first search, compare the depths, and return the appropriate node. All these solutions have a linear O(N) complexity, where N is the total number of nodes in the tree, as each node is visited exactly once. The space complexity for all the solutions is O(N) in the worst case, which occurs in skew trees (each node has only one child).