Lowest Common Ancestor of Youngest Children - codepath/compsci_guides GitHub Wiki

Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-30 mins
  • 🛠️ Topics: Binary Trees, Tree Traversal, Recursion

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What should be returned if there is only one node in the tree?
    • Return the value of that node since it is its own lowest common ancestor.
  • Can the tree have nodes with duplicate values?
    • Yes, the tree can contain duplicate node values, but that does not affect finding the lowest common ancestor.
  • What if the tree has multiple deepest leaves at different branches?
    • The lowest common ancestor should be the node where all those branches converge.
HAPPY CASE
Input: 
family1 = TreeNode("Isadora the Hexed", 
                   TreeNode("Thorne", 
                            TreeNode("Dracula"), 
                            TreeNode("Doom", TreeNode("Gloom"), TreeNode("Mortis"))), 
                   TreeNode("Raven", 
                            TreeNode("Hecate"), 
                            TreeNode("Wraith")))

Output: 
"Doom"
Explanation: 
* Gloom and Mortis are the deepest leaves. Their lowest common ancestor is Doom.

Input: 
family2 = TreeNode("Grandmama Addams", 
                   TreeNode("Gomez Addams", None, TreeNode("Wednesday Addams")), 
                   TreeNode("Uncle Fester"))

Output: 
"Wednesday Addams"
Explanation: 
* The only deepest leaf is Wednesday Addams, so it is its own lowest common ancestor.

EDGE CASE
Input: family = TreeNode("Alone")
Output: "Alone"
Explanation: The tree has only one node, so return that node's value as it is the LCA of itself.

Input: family = None
Output: None
Explanation: The tree is empty, so return `None`.

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.

For problems involving finding the lowest common ancestor (LCA) of nodes in a binary tree, we can consider the following approaches:

  • DFS Traversal: Traverse the tree to identify the deepest leaves and then use a recursive approach to find their LCA.
  • Divide and Conquer: Use a recursive function to explore the left and right subtrees to determine the LCA.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Identify Deepest Leaves:

    • Perform a DFS traversal to identify the deepest leaf nodes in the tree.
    • Track the maximum depth and store all leaves at that depth.

  2. Find LCA of Deepest Leaves:

    • Use the recursive LCA function to find the lowest common ancestor of the deepest leaves.
    • Traverse the tree starting from the root and identify where the paths to the deepest leaves converge.

  3. Return the LCA Value:

    • Return the value of the node that is the lowest common ancestor of the deepest leaves.

DFS Implementation

Pseudocode:

1) If `root` is `None`, return `None`.

2) Initialize a list `leaves` to store the deepest leaf nodes.

3) Define a recursive function `find_deepest_leaves(node, depth)`:
    a) If `node` is `None`, return.
    b) If `node` is a leaf, compare its depth with `max_depth`.
       i) If `depth` > `max_depth`, update `max_depth` and reset `leaves` with this node.
       ii) If `depth` == `max_depth`, append the node to `leaves`.
    c) Recur for left and right children.

4) Define a recursive function `lca(root, p, q)` to find the LCA of two nodes:
    a) If `root` is `None` or equals `p` or `q`, return `root`.
    b) Recur on the left and right children.
    c) If both left and right subtrees return non-`None`, return `root`.
    d) Otherwise, return the non-`None` subtree.

5) Call `find_deepest_leaves` starting from the root node.

6) Iterate through `leaves` and find their LCA using the `lca` function.

7) Return the value of the LCA node.

4: I-mplement

Implement the code to solve the algorithm.

class TreeNode:
    def __init__(self, key, value, left=None, right=None):
        self.key = key
        self.val = value
        self.left = left
        self.right = right

def find_deepest_leaves(root):
    max_depth = -1
    leaves = []
    
    def dfs(node, depth):
        nonlocal max_depth, leaves
        if not node:
            return
        
        # If this is a leaf node
        if not node.left and not node.right:
            if depth > max_depth:
                max_depth = depth
                leaves = [node]
            elif depth == max_depth:
                leaves.append(node)
        else:
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
    
    dfs(root, 0)
    return leaves

def lca(root, p, q):
    if not root or root == p or root == q:
        return root
    
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    
    if left and right:
        return root
    
    return left if left else right

def lca_youngest_children(root):
    # Step 1: Find the deepest leaves
    deepest_leaves = find_deepest_leaves(root)
    
    # Step 2: Find their LCA
    lca_node = deepest_leaves[0]
    for leaf in deepest_leaves[1:]:
        lca_node = lca(root, lca_node, leaf)
    
    return lca_node.val

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through your code with the input family1 = TreeNode("Isadora the Hexed", TreeNode("Thorne", TreeNode("Dracula"), TreeNode("Doom", TreeNode("Gloom"), TreeNode("Mortis"))), TreeNode("Raven", TreeNode("Hecate"), TreeNode("Wraith"))):
    • The DFS should correctly identify "Gloom" and "Mortis" as the deepest leaves.
    • The LCA function should return "Doom" as their lowest common ancestor.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the tree.

  • Time Complexity: O(N) because each node in the tree must be visited during the DFS traversal and the LCA computation.
  • Space Complexity: O(N) due to the recursive call stack, which can go as deep as the height of the tree.