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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Approach 1:


class Solution {

    private TreeNode ans;

    public Solution() {
        // Variable to store LCA node.
        this.ans = null;
    }

    private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) {

        // If reached the end of a branch, return false.
        if (currentNode == null) {
            return false;
        }

        // Left Recursion. If left recursion returns true, set left = 1 else 0
        int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0;

        // Right Recursion
        int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0;

        // If the current node is one of p or q
        int mid = (currentNode == p || currentNode == q) ? 1 : 0;

        // If any two of the flags left, right or mid become True
        if (mid + left + right >= 2) {
            this.ans = currentNode;
        }

        // Return true if any one of the three bool values is True.
        return (mid + left + right > 0);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Traverse the tree
        this.recurseTree(root, p, q);
        return this.ans;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Introduction

The "Lowest Common Ancestor (LCA) of a Binary Tree" problem is a common problem in binary tree algorithms. The task is to find the lowest common ancestor of two nodes in a binary tree. The LCA of two nodes is defined as the lowest node in the tree that has both nodes as descendants. In contrast to the binary search tree (BST) version, this problem does not make use of any properties such as left or right subtree ordering, making the problem more generalized.

The goal is to find the lowest node in the tree that is an ancestor of both given nodes. This problem tests understanding of tree traversal and recursion.

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The binary tree is defined as:

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

You need to implement a function to find the LCA of two given nodes in the binary tree.

Approach

To find the LCA in a binary tree, we can perform a depth-first search (DFS) from the root. The idea is to recursively explore both left and right subtrees and determine the following:

If both nodes are found in the left subtree, then the LCA lies in the left subtree.
If both nodes are found in the right subtree, then the LCA lies in the right subtree.
If one node is found in the left subtree and the other is found in the right subtree, then the current node is the LCA.

If we encounter a node that matches either of the target nodes, we return that node and continue the search in both the left and right subtrees. If we return a node from both subtrees, then the current node is their lowest common ancestor.

Algorithm

The algorithm can be broken down into the following steps:

Start from the root node and recursively search the left and right subtrees.
If the current node matches either of the target nodes, return it.
If one node is found in the left subtree and the other is found in the right subtree, the current node is the LCA.
If both nodes are found in one of the subtrees, return that subtree's result.
Finally, propagate the result up the tree until the LCA is found.

Example

Consider the following binary tree:

        Tree:
                 3
               /   \
              5     1
            /   \   /  \
           6     2 0    8
                / \
               7   4

Let's find the LCA of nodes 5 and 1: - Node 5 is in the left subtree, and node 1 is in the right subtree of root node 3. - Therefore, the LCA of nodes 5 and 1 is node 3.

Now, let's find the LCA of nodes 5 and 4: - Node 5 is in the left subtree of node 3, and node 4 is in the left subtree of node 2. - Therefore, the LCA of nodes 5 and 4 is node 5.

Code Implementation

Below is the Python implementation of the algorithm to find the LCA of two nodes in a binary tree:

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

def lowestCommonAncestor(root, p, q):
    # Base case: if root is None or root is one of the target nodes
    if not root or root == p or root == q:
        return root

    # Recur for left and right subtrees
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    # If both left and right are not None, the current node is the LCA
    if left and right:
        return root

    # If one of the subtrees is None, return the non-None child
    return left if left else right

In this code: - We recursively traverse the tree. - If the current node is null or matches one of the target nodes (p or q), we return the current node. - We recursively call the function for both the left and right subtrees. - If we find both nodes in different subtrees, the current node is their LCA. - If both nodes are found in the same subtree, the LCA is found there.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we visit each node once during the DFS traversal.

The space complexity is O(h), where h is the height of the tree. This is the space required for the recursive call stack during the traversal, which can go as deep as the height of the tree. In the worst case (unbalanced tree), the space complexity can be O(n), while in the best case (balanced tree), it is O(log n).

Conclusion

The "Lowest Common Ancestor of a Binary Tree" problem is a classic example of using recursion to solve tree problems. By recursively searching the left and right subtrees and using the LCA properties, we can efficiently find the lowest common ancestor of two nodes in any binary tree. This problem helps reinforce concepts of tree traversal, recursion, and understanding the structure of binary trees.