[Leetcode] 236. Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes pand qas the lowest node in Tthat has both pand qas descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [2, 10``5``].

-10``9`` <= Node.val <= 10``9

All Node.valare unique.

p != q

p and qwill exist in the tree.

How to understand?

LCA is Lowest Common Ancestor, find the LCA node for both p and q node. p or q node can be the LCA node itself.

When subtree found with the p or q node return the boolean, use the boolean values to check if the current node is the LCA node itself.

Or, use the parent path of node and check the ancestor of the other node in the parent path, and return the latest node as LCA node.

How to approach?

Recursive

class Solution:

    def __init__(self):
        # Variable to store LCA node.
        self.ans = None

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        def recurse_tree(current_node: TreeNode) -> bool:
            # If reached the end of a branch, return False.
            if not current_node:
                return False

            # Left Recursion
            left = recurse_tree(current_node.left)

            # Right Recursion
            right = recurse_tree(current_node.right)

            # If the current node is one of p or q
            mid = current_node == p or current_node == q


            # If any two of the three flags left, right or mid become True.
            if mid + left + right >= 2:
                self.ans = current_node

            # Return True if either of the three bool values is True.
            return mid or left or right

        # Traverse the tree
        recurse_tree(root)
        return self.ans

create ans to store the LCA node to return at the end.

create a function to call recursively which return the boolean value from the nodes.

Call the function with root value to traverse all the values in the root.

Boolean values are determined by if the node's value is p or q.

Base case is checking if the node is None, then return False.

Other than that, there are 3 different values in the function, left, right, and mid.

Left will call the function for left node, and Right will call the function for right node.

And Mid is checking the current node's value.

You can see that left → right →root order and that is DFS postorder.

and use the + operator with boolean values and check if it is same or greater than 2.

The two of them are true then set ans as current node's value.

It means the current node is the LCA itself.

In the function, return the boolean values of left, right, and mid.

Iterative, parent pointers

class Solution:

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:

        # Stack for tree traversal
        stack = [root]

        # Dictionary for parent pointers
        parent = {root: None}

        # Iterate until we find both the nodes p and q
        while p not in parent or q not in parent:

            node = stack.pop()

            # While traversing the tree, keep saving the parent pointers.
            if node.left:
                parent[node.left] = node
                stack.append(node.left)
            if node.right:
                parent[node.right] = node
                stack.append(node.right)

        # Ancestors set() for node p.
        ancestors = set()

        # Process all ancestors for node p using parent pointers.
        while p:
            ancestors.add(p)
            p = parent[p]

        # The first ancestor of q which appears in
        # p's ancestor set() is their lowest common ancestor.
        while q not in ancestors:
            q = parent[q]
        return q

This approach uses stack, parent, and ancestor.

Stack is LIFO(Last In First Out), so the top element will be poped.

Parent is like dictionary, using the stack to track the parent of each node.

Ancestor is a set checking parent of the specific node, in this case it's p node.

Initialize stack with root, and parent with root as well.

create while condition to check the p or q is not in the parent.

pop the element from the stack and set it as node.

use the node.left and node.right as parent key and parent value as node

append the node.left and node.right to stack to check the node in the while loop.

when p or q appears in parent dictionary, stop the iteration.

create ancestor set to store the parent of node p.

create while loop to check if p is not None, and add the p in ancestor replace p as the parent[p] which is p node's parent stored in parent dictionary.

when p reach the root, it will return None, so stop the iteration.

and use the q node in while condition to check the q node is not in the ancestor.

if it's not in the ancestor then replace q as the q's parent

and then when found the q in the ancestors then return the q node, since it is the LCA node.