LeetCode 1650: Lowest Common Ancestor of a Binary Tree III Solution

Master LeetCode problem 1650 (Lowest Common Ancestor of a Binary Tree III), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1650. Lowest Common Ancestor of a Binary Tree III

Medium

Hash Table Two Pointers Tree Binary Tree

Problem Explanation

Explanation:

To find the lowest common ancestor of two nodes in a binary tree, we can use a recursive approach. We start from the root and traverse the tree recursively. At each node, we check if the current node is either of the two given nodes. If it is, we return the current node as a potential common ancestor. If the current node is not either of the two nodes, we recursively search the left and right subtrees.

If both left and right subtrees return a non-null value (i.e., they found one of the nodes), then the current node is the lowest common ancestor. If only one subtree returns a non-null value, then that subtree's result is the lowest common ancestor.

Algorithm:

Start from the root node.
If the current node is null or is either of the given nodes, return the current node.
Recursively search the left and right subtrees.
If both subtrees return non-null values, the current node is the lowest common ancestor.
If only one subtree returns a non-null value, return that value.

Time Complexity: O(n) - where n is the number of nodes in the binary tree. Space Complexity: O(h) - where h is the height of the binary tree.

: :

Solution Code

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        if (p == null || q == null) {
            return null;
        }
        
        Node a = p, b = q;
        while (a != b) {
            a = a == null ? q : a.parent;
            b = b == null ? p : b.parent;
        }
        
        return a;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1650 (Lowest Common Ancestor of a Binary Tree III)?

This page provides optimized solutions for LeetCode problem 1650 (Lowest Common Ancestor of a Binary Tree III) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1650 (Lowest Common Ancestor of a Binary Tree III)?

The time complexity for LeetCode 1650 (Lowest Common Ancestor of a Binary Tree III) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1650 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1650 in Java, C++, or Python.

Back to LeetCode Solutions