Lowest Common Ancestor of a Binary Tree II

Lowest Common Ancestor of a Binary Tree II - Problem

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null.

All values of the nodes in the tree are unique. According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a binary tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

A descendant of a node x is a node y that is on the path from node x to some leaf node.

Input & Output

Example 1 — Both Nodes Exist

$ Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

› Output: 3

💡 Note: The LCA of nodes 5 and 1 is node 3. Node 5 is in the left subtree of 3, and node 1 is in the right subtree of 3.

Example 2 — One Node is Ancestor

$ Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

› Output: 5

💡 Note: The LCA of nodes 5 and 4 is node 5, since a node can be a descendant of itself. Node 4 is in the subtree of node 5.

Example 3 — Node Doesn't Exist

$ Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10

› Output: null

💡 Note: Node 10 does not exist in the tree, so we return null instead of finding an LCA.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
-10⁹ ≤ Node.val ≤ 10⁹
All Node.val are unique
p ≠ q

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes p=5 and q=1 to find LCA

Verify Existence

Confirm both target nodes exist in the tree

Find LCA

Return lowest node that has both as descendants

Key Takeaway

🎯 Key Insight: Must verify both nodes exist in the tree before finding their lowest common ancestor

Asked in

f Facebook 35 M Microsoft 28 a Amazon 22 G Google 18

The key insight is that we must verify both nodes exist before finding their LCA. The optimal approach uses a single DFS traversal that simultaneously checks existence and finds the lowest common ancestor. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Node	O(n²)	O(h)	For each node, check if it can be the LCA by searching its subtrees
DFS with Existence Check	O(n)	O(h)	Use DFS to find LCA while tracking if both nodes exist

Brute Force - Check Every Node — Algorithm Steps

Step 1: Search entire tree to verify p exists
Step 2: Search entire tree to verify q exists
Step 3: For each node, check if it's the LCA by searching subtrees
Step 4: Return the lowest node that has both p and q in its subtrees

Visualization

Tap to expand

Step-by-Step Walkthrough

Verify Existence

Search tree to confirm both p and q exist

Check Each Node

For each node, search left and right subtrees

Find LCA

Return lowest node that has p in one subtree and q in another

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

bool findNode(struct TreeNode* node, int target) {
    if (!node) return false;
    if (node->val == target) return true;
    return findNode(node->left, target) || findNode(node->right, target);
}

struct TreeNode* findLCA(struct TreeNode* node, int p, int q) {
    if (!node) return NULL;
    
    bool leftHasP = findNode(node->left, p);
    bool leftHasQ = findNode(node->left, q);
    bool rightHasP = findNode(node->right, p);
    bool rightHasQ = findNode(node->right, q);
    
    bool isP = node->val == p;
    bool isQ = node->val == q;
    
    if (((leftHasP || isP) && (rightHasQ || isQ)) || ((leftHasQ || isQ) && (rightHasP || isP))) {
        return node;
    }
    
    if (leftHasP && leftHasQ) {
        return findLCA(node->left, p, q);
    }
    if (rightHasP && rightHasQ) {
        return findLCA(node->right, p, q);
    }
    
    return NULL;
}

int* solution(struct TreeNode* root, int p, int q) {
    if (!root) return NULL;
    
    if (!findNode(root, p) || !findNode(root, q)) {
        return NULL;
    }
    
    struct TreeNode* lca = findLCA(root, p, q);
    if (lca) {
        int* result = (int*)malloc(sizeof(int));
        *result = lca->val;
        return result;
    }
    return NULL;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // For simplicity, create a test tree manually
    struct TreeNode* root = createNode(3);
    root->left = createNode(5);
    root->right = createNode(1);
    root->left->left = createNode(6);
    root->left->right = createNode(2);
    root->right->left = createNode(0);
    root->right->right = createNode(8);
    root->left->right->left = createNode(7);
    root->left->right->right = createNode(4);
    
    int p = 5, q = 1;
    int* result = solution(root, p, q);
    
    if (result) {
        printf("%d\n", *result);
        free(result);
    } else {
        printf("null\n");
    }
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we potentially search the entire subtree

⚠ Quadratic Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

23.4K Views

Medium-High Frequency

~18 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Node — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler