Jan 9

LC-865: Smallest Subtree with all the Deepest Nodes (Rust)

	So I knew it is going to be a DFS approach, going down the tree following the root. To quickly help refresh my memory, I did the max depth of a tree LC, and got the most optimal answer in a single pass: https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
- Base case: If node is None, return 0 
- Recursively get the max depth of left and right subtrees 
- Return the maximum of the two depths + 1 (for current node) 
- Single pass solution with O(n) time complexity
```
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let Some(rc_node) = root else {
            return 0;
        };

        let node_val = rc_node.borrow();

        let l_height = Self::max_depth(node_val.left.clone());
        let r_height = Self::max_depth(node_val.right.clone());

        return l_height.max(r_height) + 1
    }
}
```

Back to the original question:
So my approach here involves going deep also. 
DFS with tracking both subtree AND depth 

2 things: I need to return TWO pieces of information from each recursive call: 
1. The subtree that contains all the deepest nodes 
2. The depth/distance to the deepest nodes from this point

```
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn subtree_with_all_deepest(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        return Self::dfs(root).0
    }

    fn dfs(node: Option<Rc<RefCell<TreeNode>>>) -> (Option<Rc<RefCell<TreeNode>>>, i32)  {
        let Some(rc_node) = node else {
            return (None, 0);
        };

        let node_ref = rc_node.borrow();
        let left = node_ref.left.clone();
        let right = node_ref.right.clone();
        drop(node_ref);

        let (l_node, l_dist) = Self::dfs(left);
        let (r_node, r_dist) = Self::dfs(right);

        if l_dist > r_dist {
            return (l_node, l_dist + 1)
        } else if r_dist > l_dist {
            return (r_node, r_dist + 1)
        } else {
            return (Some(rc_node), l_dist + 1)
        }
    }
}
```

Why tuple? 
- Just returning depth isn't enough - I need to know which subtree has the deepest nodes - 
Also returning the subtree isn't enough - I need to compare depths to make decisions 

Logic breakdown: 
- Base case: Empty node returns (None, 0) - no subtree, depth is 0 
- Recursively get results from both left and right children - Compare the depths: 
	- If `l_dist > r_dist`: All deepest nodes are in the left subtree only, so return the left subtree and its depth + 1 
	- If `r_dist > l_dist`: All deepest nodes are in the right subtree only, so return the right subtree and its depth + 1 
	- If `l_dist == r_dist`: Both subtrees reach the same depth, meaning the deepest nodes are on BOTH sides. 

The current node is the Lowest Common Ancestor (LCA) of all deepest nodes, so return the current node itself with depth + 1 

Key difference from max_depth: - Max depth: only care about the NUMBER (depth).
This problem: care about the LOCATION (which subtree) AND the depth.

Solution: Return both as a tuple and use depth to determine which subtree to propagate upward The main function just extracts the subtree (`.0`) from the final result and discards the depth.

Time Complexity: O(n) - visit each node once 
Space Complexity: O(h) - recursion stack where h is tree height