236. Lowest Common Ancestor Binary Tree Solution

Q: Is Lowest Common Ancestor of a Binary Tree easy or hard?

Lowest Common Ancestor of a Binary Tree is generally classified as a Medium difficulty problem. The recursion logic is simple once you understand how subtree results propagate upward, but recognizing the split-point insight can take practice.

Q: Lowest Common Ancestor of a Binary Tree Python/Java solution

Most implementations use recursive DFS in Python, Java, C++, or JavaScript. The function checks whether p or q exists in the left or right subtree and returns the current node when both sides contain one target node each.

Q: How to solve Lowest Common Ancestor of a Binary Tree in O(n)?

Run a recursive DFS from the root. If the current node equals p or q, return it. Recursively search the left and right subtrees. When both sides return non-null values, the current node is the lowest common ancestor. Each node is processed once, giving O(n) time complexity.

Q: What is the best approach for Lowest Common Ancestor of a Binary Tree?

The recursive Depth-First Search approach is considered the best solution. It traverses the tree once and determines the split point where nodes p and q appear in different subtrees. This method runs in O(n) time and uses O(h) space for the recursion stack, where h is the tree height.

Q: Is Lowest Common Ancestor of a Binary Tree asked at Google/Amazon/Meta?

Lowest Common Ancestor is a classic tree interview question and appears frequently at companies like Google, Amazon, Meta, and Microsoft. Variants also appear in system design and advanced tree problems, making it a foundational concept for technical interviews.

Q: What data structure is used in Lowest Common Ancestor of a Binary Tree?

The problem primarily uses a binary tree data structure combined with Depth-First Search traversal. Some alternative solutions also store root-to-node paths using arrays or lists to compare ancestors.

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

The standard solution runs in O(n) time because each node in the binary tree may be visited once during the DFS traversal. Space complexity is O(h) due to the recursion stack, where h represents the height of the tree.

The problem

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,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [2, 10⁵].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
p != q
p and q will exist in the tree.

Approach overview

Problem Overview: Given the root of a binary tree and two nodes p and q, return their lowest common ancestor (LCA). The LCA is the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).

Approach 1: Path to Root Approach (O(n) time, O(n) space)

This approach records the path from the root to each target node. Run a DFS to build a list of nodes from the root to p, then repeat for q. Once both paths are available, iterate through them from the start and find the last common node before the paths diverge. That node is the lowest common ancestor. The tree traversal takes O(n) time in the worst case, and storing both paths requires O(n) extra space.

The method is easy to reason about because it converts the problem into comparing two arrays of ancestors. It works well when you want a clear conceptual model of ancestor relationships. The downside is the extra memory used to store both paths.

Approach 2: Recursive Depth-First Search (O(n) time, O(h) space)

This is the standard optimal solution. Traverse the tree using recursive DFS. If the current node is null, return null. If the current node matches p or q, return that node. Recursively search the left and right subtrees. If both recursive calls return non-null values, the current node is the first point where the two targets split across subtrees, making it the lowest common ancestor.

If only one side returns a node, propagate that result upward. Eventually the recursion bubbles the correct ancestor back to the root call. Each node is visited once, giving O(n) time complexity. The recursion stack consumes O(h) space where h is the tree height.

This approach works naturally with Tree recursion patterns and is commonly used in Depth-First Search problems. Since binary tree traversal is already required, the solution stays simple and avoids storing full paths.

Recommended for interviews: The recursive DFS solution is what interviewers typically expect. It demonstrates strong understanding of Binary Tree traversal and recursive reasoning. Mentioning the path-to-root approach first shows you understand the problem structure, but implementing the DFS solution proves you can optimize both memory usage and code simplicity.

Approach 1: Recursive Depth-First Search

This approach uses recursion to traverse the tree starting from the root. If the current node is either p or q, then the node is returned upwards in the recursion stack as the potential LCA. Otherwise, we continue to search both left and right subtrees. If both subtrees return non-null values, it means p and q are in different subtrees, and the current node is the LCA. If only one subtree returns a non-null value, it means both nodes are located in that subtree and that subtree's root should be the LCA.

Python

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left if left else right

Java

public 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;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

C++

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

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

JavaScript

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

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

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

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

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL || root == p || root == q) return root;
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left != NULL && right != NULL) return root;
    return left != NULL ? left : right;
}

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public 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;
    }
}

This Python solution works similarly to what has been described for other languages. The recursion checks for the base case and evaluates subtrees recursively, returning the appropriate node.

Complexity

Time Complexity: O(N) with N as the node count.
Space Complexity: O(N) due to recursion call stack in worst-case tall trees.

Try this approach in the editor

Approach 2: Path to Root Approach

The basic idea is to find the paths from the root to the two nodes p and q. Once you have the paths, compare them to find the deepest common node. This method is straightforward, using known operations to reconfirm ancestor status along determined paths.

Python

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

class Solution:
    def getPath(self, root, target, path):
        if not root:
            return False
        path.append(root)
        if root == target:
            return True
        if (root.left and self.getPath(root.left, target, path)) or \
           (root.right and self.getPath(root.right, target, path)):
            return True
        path.pop(-1)
        return False

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        pathP, pathQ = [], []
        self.getPath(root, p, pathP)
        self.getPath(root, q, pathQ)
        i = 0
        while i < len(pathP) and i < len(pathQ) and pathP[i] == pathQ[i]:
            i += 1
        return pathP[i - 1]

Java

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private boolean getPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) return false;
        path.add(root);
        if (root == target) return true;
        if (root.left != null && getPath(root.left, target, path) || 
            root.right != null && getPath(root.right, target, path))
            return true;
        path.remove(path.size() - 1);
        return false;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new ArrayList<>(), pathQ = new ArrayList<>();
        getPath(root, p, pathP);
        getPath(root, q, pathQ);
        int i;
        for (i = 0; i < pathP.size() && i < pathQ.size(); i++) {
            if (!pathP.get(i).equals(pathQ.get(i))) break;
        }
        return pathP.get(i - 1);
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool getPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {
    if (!root) return false;
    path.push_back(root);
    if (root == target) return true;
    if ((root->left && getPath(root->left, target, path)) || 
        (root->right && getPath(root->right, target, path)))
        return true;
    path.pop_back();
    return false;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    vector<TreeNode*> pathP, pathQ;
    getPath(root, p, pathP);
    getPath(root, q, pathQ);
    int i;
    for (i = 0; i < pathP.size() && i < pathQ.size(); i++) {
        if (pathP[i] != pathQ[i]) break;
    }
    return pathP[i - 1];
}

JavaScript

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

function getPath(root, target, path) {
    if (!root) return false;
    path.push(root);
    if (root === target) return true;
    if ((root.left && getPath(root.left, target, path)) || 
        (root.right && getPath(root.right, target, path))) {
        return true;
    }
    path.pop();
    return false;
}

function lowestCommonAncestor(root, p, q) {
    const pathP = [];
    const pathQ = [];
    getPath(root, p, pathP);
    getPath(root, q, pathQ);
    let i = 0;
    while (i < pathP.length && i < pathQ.length && pathP[i] === pathQ[i]) {
        i++;
    }
    return pathP[i - 1];
}

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

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

int getPath(struct TreeNode* root, struct TreeNode* target, struct TreeNode* path[], int *pathLen) {
    if (!root) return 0;
    path[(*pathLen)++] = root;
    if (root == target)
        return 1;
    if (getPath(root->left, target, path, pathLen) || getPath(root->right, target, path, pathLen))
        return 1;
    (*pathLen)--;
    return 0;
}

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    struct TreeNode* pathP[1000], *pathQ[1000];
    int pathPLen = 0, pathQLen = 0;
    getPath(root, p, pathP, &pathPLen);
    getPath(root, q, pathQ, &pathQLen);
    int i;
    for (i = 0; i < pathPLen && i < pathQLen; i++) {
        if (pathP[i] != pathQ[i])
            break;
    }
    return pathP[i - 1];
}

using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    private bool GetPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) return false;
        path.Add(root);
        if (root == target) return true;
        if ((root.left != null && GetPath(root.left, target, path)) ||
            (root.right != null && GetPath(root.right, target, path)))
            return true;
        path.RemoveAt(path.Count - 1);
        return false;
    }

    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new List<TreeNode>(), pathQ = new List<TreeNode>();
        GetPath(root, p, pathP);
        GetPath(root, q, pathQ);
        int i;
        for (i = 0; i < pathP.Count && i < pathQ.Count; i++) {
            if (pathP[i] != pathQ[i]) break;
        }
        return pathP[i - 1];
    }
}

This Python implementation uses two path lists to track node descent from root to the two target nodes, returning the last common node.

Complexity

Time Complexity: O(N) because of path traversal.
Space Complexity: O(H) for storing paths, where H is the tree height.

Try this approach in the editor

Approach 3: Recursion

We recursively traverse the binary tree:

If the current node is null or equals to p or q, then we return the current node;

Otherwise, we recursively traverse the left and right subtrees, and record the returned results as left and right. If both left and right are not null, it means that p and q are in the left and right subtrees respectively, so the current node is the nearest common ancestor; If only one of left and right is not null, we return the one that is not null.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	}
	if left != nil {
		return left
	}
	return right
}

Rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn lowest_common_ancestor(
        root: Option<Rc<RefCell<TreeNode>>>,
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if root.is_none() || root == p || root == q {
            return root;
        }
        let left = Self::lowest_common_ancestor(
            root.as_ref().unwrap().borrow().left.clone(),
            p.clone(),
            q.clone(),
        );
        let right = Self::lowest_common_ancestor(
            root.as_ref().unwrap().borrow().right.clone(),
            p.clone(),
            q.clone(),
        );
        if left.is_some() && right.is_some() {
            return root;
        }
        if left.is_none() {
            return right;
        }
        return left;
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Depth-First Search	Time Complexity: `O(N)` with `N` as the node count. Space Complexity: `O(N)` due to recursion call stack in worst-case tall trees.
Path to Root Approach	Time Complexity: `O(N)` because of path traversal. Space Complexity: `O(H)` for storing paths, where H is the tree height.
Recursion	–

Complexity analysis

Approach	Time	Space	When to Use
Path to Root Approach	O(n)	O(n)	Useful for understanding ancestor relationships or when explicit root-to-node paths are required.
Recursive Depth-First Search	O(n)	O(h)	Best general solution for binary trees. Minimal extra memory and standard interview approach.

Frequently asked questions

Is Lowest Common Ancestor of a Binary Tree easy or hard?

Lowest Common Ancestor of a Binary Tree is generally classified as a Medium difficulty problem. The recursion logic is simple once you understand how subtree results propagate upward, but recognizing the split-point insight can take practice.

Lowest Common Ancestor of a Binary Tree Python/Java solution

Most implementations use recursive DFS in Python, Java, C++, or JavaScript. The function checks whether p or q exists in the left or right subtree and returns the current node when both sides contain one target node each.

How to solve Lowest Common Ancestor of a Binary Tree in O(n)?

Run a recursive DFS from the root. If the current node equals p or q, return it. Recursively search the left and right subtrees. When both sides return non-null values, the current node is the lowest common ancestor. Each node is processed once, giving O(n) time complexity.

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

The recursive Depth-First Search approach is considered the best solution. It traverses the tree once and determines the split point where nodes p and q appear in different subtrees. This method runs in O(n) time and uses O(h) space for the recursion stack, where h is the tree height.

Is Lowest Common Ancestor of a Binary Tree asked at Google/Amazon/Meta?

Lowest Common Ancestor is a classic tree interview question and appears frequently at companies like Google, Amazon, Meta, and Microsoft. Variants also appear in system design and advanced tree problems, making it a foundational concept for technical interviews.

What data structure is used in Lowest Common Ancestor of a Binary Tree?

The problem primarily uses a binary tree data structure combined with Depth-First Search traversal. Some alternative solutions also store root-to-node paths using arrays or lists to compare ancestors.

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

The standard solution runs in O(n) time because each node in the binary tree may be visited once during the DFS traversal. Space complexity is O(h) due to the recursion stack, where h represents the height of the tree.

Lowest Common Ancestor of a Binary Tree solution and explanation

The problem

Approach overview

Approach 1: Recursive Depth-First Search

Approach 2: Path to Root Approach

Approach 3: Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Lowest Common Ancestor of a Binary Tree solution and explanation

The problem

Approach overview

Approach 1: Recursive Depth-First Search

Approach 2: Path to Root Approach

Approach 3: Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems