LC 0865 [M] Smallest Subtree with all the Deepest Nodes - ALawliet/algorithms GitHub Wiki

trick is to calculate the height from the bottom up

/**
 * The question is unclear. For example, if we did not have nodes 7 and 4, the answer would
 * be TreeNode(3). If we did not have node 4, the answer would be TreeNode(7) and not
 * TreeNode(2). Similarly, if we did not have 7, the answer would be TreeNode(4) and not
 * TreeNode(2).
 *
 * Intuitively, we should be traversing from the children to the parent and calculate the
 * height from bottom. So the null nodes would have height 0. The leaf nodes would have the
 * height 1 and the root would have the max height.
 
 * At each node, we keep a pair<height_of_node_from_bottom, node>. At a given node, if we
 * realize that the leftHeight == rightHeight, it means we have found the deepest subtree
 * rooted at node. If leftHeight > rightHeight, it means the deepest subtree must be rooted
 * at left child. If rightHeight > leftHeight, it means the deepest subtree must be rooted
 * at right child.
 
 * Which traversal allows us to traverse from bottom-up? Postorder! So we use it in the code.
 */

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root):
            # return (height, parent)
            def height(node):
                if not node:
                    return (0, None)
                
                l = height(node.left)
                r = height(node.right)
                
                if l[0] == r[0]:
                    return (l[0] + 1, node) # can return (l[0] or r[0] + 1, ancestor)
                
                elif l[0] > r[0]:
                    return (l[0] + 1, l[1])
                elif l[0] < r[0]:
                    return (r[0] + 1, r[1])
      
                
            return height(root)[1]