Lowest Common Ancestor of a Binary Tree — DSA

Problem#

Given the root of a binary tree and two nodes p and q, return their lowest common ancestor (LCA) — the deepest node having both as descendants (a node can be its own descendant).

Examples#

For [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 → 3.
p = 5, q = 4 → 5.

Constraints#

The number of nodes is in [2, 10^5]. Both p and q exist in the tree.

Approach#

Recursive search. Return the current node if it equals p or q. Recurse into left and right. If both return non-null, the current node is the LCA. Otherwise return whichever is non-null.

Solution#

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode* l = lowestCommonAncestor(root->left, p, q);
        TreeNode* r = lowestCommonAncestor(root->right, p, q);
        if (l && r) return root;
        return l ? l : r;
    }
};

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    l := lowestCommonAncestor(root.Left, p, q)
    r := lowestCommonAncestor(root.Right, p, q)
    if l != nil && r != nil {
        return root
    }
    if l != nil {
        return l
    }
    return r
}

from typing import Optional

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> Optional['TreeNode']:
        if root is None or root is p or root is q:
            return root
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)
        if l and r:
            return root
        return l if l else r

function lowestCommonAncestor(root, p, q) {
    if (root === null || root === p || root === q) return root;
    const l = lowestCommonAncestor(root.left, p, q);
    const r = lowestCommonAncestor(root.right, p, q);
    if (l && r) return root;
    return l ? l : r;
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        if (l != null && r != null) return root;
        return l != null ? l : r;
    }
}

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if (root === null || root === p || root === q) return root;
    const l = lowestCommonAncestor(root.left, p, q);
    const r = lowestCommonAncestor(root.right, p, q);
    if (l && r) return root;
    return l ?? r;
}

Editorial#

The recursive contract: each call returns the LCA within its subtree if both targets exist there, otherwise the single target found, otherwise null. Whenever a node receives non-null from both subtrees, it sits between p and q and is the LCA.

Complexity#

Time: O(n).
Space: O(h).

Concept revision#

Lowest Common Ancestor of a Binary Search Tree

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#