What is the time complexity of Lowest Common Ancestor of a Binary Tree?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Lowest Common Ancestor of a Binary Tree?

This problem uses Tree, Depth-First Search, Binary Tree. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Lowest Common Ancestor of a Binary Tree?

Insight 1: The core idea is to use a recursive Depth-First Search (DFS) to traverse the tree. If we find either `p` or `q`, we return it up the call stack. This is because either `p` or `q` could be the LCA. Insight 2: The recursive calls will propagate upward. If at any node, the left subtree returns `p` and the right subtree returns `q` (or vice-versa), then that node is the LCA because it is the lowest node that contains both `p` and `q` as descendants.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Lowest Common Ancestor of a Binary Tree - LeetCode 236 Solution

Q: Which companies ask LeetCode 236. Lowest Common Ancestor of a Binary Tree in interviews?

This problem is frequently asked at Atlassian, BitGo, Flipkart, GE Healthcare, Intuit and 8 more companies.

Lowest Common Ancestor of a Binary Tree - Complete Solution Guide

Lowest Common Ancestor of a Binary Tree is LeetCode problem 236, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 ).” 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,nu

Detailed Explanation

The problem asks us to find the Lowest Common Ancestor (LCA) of two given nodes, `p` and `q`, in a binary tree. The LCA is defined as the lowest node in the tree that has both `p` and `q` as descendants (including the possibility that a node can be a descendant of itself). The input consists of the root of a binary tree and the two nodes `p` and `q` that are guaranteed to exist in the tree and are distinct. The output should be the TreeNode representing the LCA of `p` and `q`. The number of nodes in the tree is between 2 and 10^5, node values are unique and within a specified range.

Solution Approach

The solution uses a recursive DFS traversal of the binary tree. The recursion effectively searches the left and right subtrees for the target nodes `p` and `q`. The function returns a node when either of the following conditions are met: the current node is null, the current node is one of the target nodes, or the current node is the LCA. The magic happens in the recursive calls and how their results are combined.

Step-by-Step Algorithm

Step 1: Base Case: If the current node `root` is null or if `root` is equal to `p` or `q`, return `root` immediately. This is because either we've reached the end of a branch, or we've found one of the nodes we're looking for.
Step 2: Recursive Calls: Recursively call the function on the left and right subtrees: `left = lowestCommonAncestor(root.left, p, q)` and `right = lowestCommonAncestor(root.right, p, q)`. These calls explore the subtrees.
Step 3: Check for LCA: After the recursive calls return, check if both `left` and `right` are non-null. If both are non-null, it means that one of the target nodes (`p` or `q`) was found in the left subtree and the other was found in the right subtree. In this case, the current `root` is the LCA, so return `root`.
Step 4: Return Results: If only one of `left` or `right` is non-null, it means that one of the subtrees contains either one of the target nodes or the LCA of the target nodes. Return the non-null value. If both `left` and `right` are null, it means neither `p` nor `q` were found in the current subtree, so return `null`.

Key Insights

Insight 1: The core idea is to use a recursive Depth-First Search (DFS) to traverse the tree. If we find either `p` or `q`, we return it up the call stack. This is because either `p` or `q` could be the LCA.
Insight 2: The recursive calls will propagate upward. If at any node, the left subtree returns `p` and the right subtree returns `q` (or vice-versa), then that node is the LCA because it is the lowest node that contains both `p` and `q` as descendants.
Insight 3: If only one of the subtrees returns a node, then that node is either the LCA (if the other node is a descendant of it) or one of the target nodes (`p` or `q`) itself.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Tree, Depth-First Search, Binary Tree.

Companies

Asked at: Atlassian, BitGo, Flipkart, GE Healthcare, Intuit, LinkedIn, MongoDB, Myntra, Oracle, Salesforce, Snapdeal, Wix, Yandex.

Lowest Common Ancestor of a Binary Tree | LeetCode 236

Medium

Tree Depth-First Search Binary Tree

Time: O(n)Space: O(n)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        }
        
        return (left != null) ? left : right;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 236: Lowest Common Ancestor of a Binary Tree - Detailed explanation and solution approaches.

Topics

Tree Depth-First Search Binary Tree

Companies

AtlassianBitGoFlipkartGE HealthcareIntuitLinkedInMongoDBMyntra

Stats

Difficulty:Medium

Languages:4

Companies:13

Problem #:236

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: Base Case: If the current node `root` is null or if `root` is equal to `p` or `q`, return `root` immediately. This is because either we've reached the end of a branch, or we've found one of the nodes we're looking for.
2
Step 2: Recursive Calls: Recursively call the function on the left and right subtrees: `left = lowestCommonAncestor(root.left, p, q)` and `right = lowestCommonAncestor(root.right, p, q)`. These calls explore the subtrees.
3
Step 3: Check for LCA: After the recursive calls return, check if both `left` and `right` are non-null. If both are non-null, it means that one of the target nodes (`p` or `q`) was found in the left subtree and the other was found in the right subtree. In this case, the current `root` is the LCA, so return `root`.
4
Step 4: Return Results: If only one of `left` or `right` is non-null, it means that one of the subtrees contains either one of the target nodes or the LCA of the target nodes. Return the non-null value. If both `left` and `right` are null, it means neither `p` nor `q` were found in the current subtree, so return `null`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(n) because, in the worst case, the algorithm visits each node in the tree once. The space complexity is O(n) due to the maximum depth of the recursive call stack, which can be equal to the number of nodes in a skewed tree.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Approach with Parent Pointers

An iterative approach would involve using a hash map to store the parent pointers of each node in the tree. Then, we can traverse from `p` and `q` up to the root, and find the first common ancestor. First find the depths of p and q. Go to the same level, and then traverse upwards together.

Time: O(n), where n is the number of nodes.Space: O(n), where n is the number of nodes, to store the parent pointers in the hash map.

Trade-offs: This approach avoids recursion and the associated call stack overhead, but it requires extra space to store the parent pointers.

✨

Key Insights

1Insight 1: The core idea is to use a recursive Depth-First Search (DFS) to traverse the tree. If we find either `p` or `q`, we return it up the call stack. This is because either `p` or `q` could be the LCA.
2Insight 2: The recursive calls will propagate upward. If at any node, the left subtree returns `p` and the right subtree returns `q` (or vice-versa), then that node is the LCA because it is the lowest node that contains both `p` and `q` as descendants.
3Insight 3: If only one of the subtrees returns a node, then that node is either the LCA (if the other node is a descendant of it) or one of the target nodes (`p` or `q`) itself.

📚

Key Terms Explained

For Students

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: `p` is an ancestor of `q` (or vice versa). The algorithm correctly identifies `p` (or `q`) as the LCA. For example, if `p` is the root and `q` is deep within the left subtree, the algorithm will correctly return `p`.
Edge case 2: `p` and `q` are not in the tree. The problem states that both p and q are guaranteed to be present, so there's no need to consider cases where one or both are missing.
Edge case 3: `root` is `p` or `q`. This is handled correctly because if `root == p || root == q` the function immediately returns `root`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting the base case where the root is equal to p or q. This results in incorrect LCA identification when p or q is an ancestor of the other.

✗Common mistake 2: Not understanding that the LCA can be one of the nodes itself (p or q).

✗Common mistake 3: Assuming that the tree is balanced, which is not guaranteed, leading to incorrect space complexity assumptions. The tree can be skewed.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: In file systems, finding the common ancestor directory of two files.

🏦Real-world scenario 2: In organizational charts, determining the common manager between two employees.

🎮Real-world scenario 3: In phylogenetic trees, finding the most recent common ancestor of two species.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Most tree problems can be solved recursively. The base case is usually a null node. Think about what information needs to flow up vs down the tree.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Not handling null nodes properly. Always check if the current node exists before accessing its children.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 27, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

How do I choose between recursive and iterative tree traversal?

Use recursive traversal for cleaner code when stack depth isn't a concern (tree height < ~1000). Use iterative with explicit stack for very deep trees to avoid stack overflow. Iterative is also preferred when you need fine-grained control over the traversal process.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Lowest Common Ancestor of a Binary Tree"?

For this medium-level Tree problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?