# How to Find the Lowest Common Ancestor (LCA) in a Binary Tree > Learn how to find the Lowest Common Ancestor in a binary tree using a recursive DFS approach. Get the optimal solution for this common interview question. - Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews) - Tags: how-to-guide - Published: 2026-03-04 --- **Use a recursive post-order DFS that returns a node when it finds either target, and when both left and right subtrees return non-null values, the current node is the LCA.** Finding the **lowest common ancestor (LCA)** in a binary tree is a fundamental algorithmic problem frequently encountered in technical interviews and tree-based data processing. This guide examines the optimal recursive solution implemented in the [kdn251/interviews](https://github.com/kdn251/interviews) repository, providing a complete breakdown of how to find the LCA in a binary tree with `O(N)` time complexity. ## What Is the Lowest Common Ancestor in a Binary Tree? The **lowest common ancestor (LCA)** of two nodes `p` and `q` in a binary tree is defined as the deepest node that has both `p` and `q` as descendants, where a node is considered a descendant of itself. In practical terms, the LCA represents the shared parent node located farthest from the root where the paths to both target nodes diverge. ## Recursive DFS Approach to Find LCA in a Binary Tree The most efficient method to locate the LCA employs a **post-order depth-first search (DFS)** that traverses from the leaves upward, propagating node references only when targets are discovered. ### Algorithm Logic The recursive strategy follows three distinct phases: 1. **Base case handling** – If the current `root` is `null`, or if `root` matches either `p` or `q`, immediately return `root`. This captures the scenario where one target is the ancestor of the other. 2. **Subtree exploration** – Recursively invoke the LCA search on `root.left` and `root.right` to probe both subtrees for the target nodes. 3. **Result combination** – - If **both** left and right recursive calls return non-`null` values, the current `root` represents the split point where `p` and `q` reside in different subtrees, making `root` the LCA. - If only **one** side returns a non-`null` node, propagate that result upward, as it contains either one of the targets or the LCA discovered deeper in that branch. ### Complexity Analysis - **Time Complexity:** `O(N)` where *N* is the number of nodes in the tree. The algorithm visits each node exactly once in the worst case. - **Space Complexity:** `O(H)` where *H* is the height of the tree, representing the maximum recursion stack depth. In a skewed tree, this degrades to `O(N)`, while a balanced tree requires `O(log N)`. ## Java Implementation from kdn251/interviews The [kdn251/interviews](https://github.com/kdn251/interviews) repository provides a clean, production-ready implementation in [`leetcode/tree/LowestCommonAncestorOfABinaryTree.java`](https://github.com/kdn251/interviews/blob/main/leetcode/tree/LowestCommonAncestorOfABinaryTree.java). The `lowestCommonAncestor` method implements the exact recursive post-order strategy described above: ```java public class LowestCommonAncestorOfABinaryTree { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; // base case } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) { // p on one side, q on the other return root; // current node is LCA } return left == null ? right : left; // propagate non-null result } } ``` This implementation handles all edge cases, including scenarios where one node is the direct ancestor of the other, by returning immediately when a match is found and allowing that result to propagate upward. ## Practical Examples ### Basic Usage Consider a binary tree structured as follows: ``` 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 ``` To find the LCA of nodes 5 and 1: ```java // Construct the tree TreeNode root = new TreeNode(3); root.left = new TreeNode(5); root.right = new TreeNode(1); // ... (additional node construction) LowestCommonAncestorOfABinaryTree solver = new LowestCommonAncestorOfABinaryTree(); TreeNode lca = solver.lowestCommonAncestor(root, root.left, root.right); System.out.println(lca.val); // Output: 3 ``` To find the LCA of nodes 5 and 4 (where 5 is the ancestor of 4): ```java TreeNode node4 = root.left.right.right; // Node with value 4 TreeNode lca2 = solver.lowestCommonAncestor(root, root.left, node4); System.out.println(lca2.val); // Output: 5 ``` ### Edge Cases The algorithm gracefully handles several boundary conditions: - **One node is the ancestor of the other** – The base case `if (root == null || root == p || root == q)` immediately returns the current node when it matches either target. If one target is the ancestor of the other, the ancestor will be encountered first and returned, then propagated upward as the LCA without further searching the descendant's subtree. - **One or both nodes missing** – If either `p` or `q` does not exist in the tree, the algorithm returns the existing node (or `null` if neither exists), as only the found node propagates upward. - **Identical nodes** – When `p` and `q` refer to the same node, the base case triggers on the first encounter and returns that node immediately. ## Repository Structure and Related Files The [kdn251/interviews](https://github.com/kdn251/interviews) repository organizes this solution across multiple interview preparation tracks. The core implementation resides in the LeetCode section, with identical copies adapted for specific company interview sets: | Path | Description | |------|-------------| | [leetcode/tree/LowestCommonAncestorOfABinaryTree.java](https://github.com/kdn251/interviews/blob/master/leetcode/tree/LowestCommonAncestorOfABinaryTree.java) | Core recursive solution for LeetCode problem 236. | | [company/amazon/LowestCommonAncestorOfABinaryTree.java](https://github.com/kdn251/interviews/blob/master/company/amazon/LowestCommonAncestorOfABinaryTree.java) | Amazon interview preparation variant. | | [company/facebook/LowestCommonAncestorOfABinaryTree.java](https://github.com/kdn251/interviews/blob/master/company/facebook/LowestCommonAncestorOfABinaryTree.java) | Facebook interview preparation variant. | | [company/linkedin/LowestCommonAncestorOfABinaryTree.java](https://github.com/kdn251/interviews/blob/master/company/linkedin/LowestCommonAncestorOfABinaryTree.java) | LinkedIn interview preparation variant. | | [company/twitter/LowestCommonAncestorOfABinaryTree.java](https://github.com/kdn251/interviews/blob/master/company/twitter/LowestCommonAncestorOfABinaryTree.java) | Twitter interview preparation variant. | All implementations share the identical `O(N)` time and `O(H)` space recursive strategy, ensuring consistent performance across different interview contexts. ## Summary - The **lowest common ancestor (LCA)** in a binary tree is the deepest node where paths to two target nodes diverge. - The optimal solution uses **post-order DFS recursion** with `O(N)` time complexity and `O(H)` space complexity. - The algorithm returns immediately when encountering `null`, `p`, or `q`, then propagates the first non-null result upward until both left and right subtrees return values, identifying the LCA. - The [kdn251/interviews](https://github.com/kdn251/interviews) repository provides this implementation in [`leetcode/tree/LowestCommonAncestorOfABinaryTree.java`](https://github.com/kdn251/interviews/blob/main/leetcode/tree/LowestCommonAncestorOfABinaryTree.java) and across multiple company-specific interview directories. ## Frequently Asked Questions ### What is the time complexity of finding the LCA in a binary tree? The recursive DFS approach runs in **O(N)** time where *N* is the number of nodes, because in the worst case it must visit every node in the tree once to locate both target nodes. ### Can the LCA algorithm handle cases where one node is the ancestor of the other? Yes. The base case `if (root == null || root == p || root == q)` immediately returns the current node when it matches either target. If one target is the ancestor of the other, the ancestor will be encountered first and returned, then propagated upward as the LCA without further searching the descendant's subtree. ### What is the space complexity of the recursive LCA solution? The space complexity is **O(H)** where *H* is the height of the tree, representing the maximum recursion stack depth. In a balanced binary tree this is `O(log N)`, but it degrades to `O(N)` in a skewed tree where each node has only one child. ### Where can I find the complete implementation in the kdn251/interviews repository? The primary implementation resides in [`leetcode/tree/LowestCommonAncestorOfABinaryTree.java`](https://github.com/kdn251/interviews/blob/main/leetcode/tree/LowestCommonAncestorOfABinaryTree.java). Identical copies adapted for specific company interview tracks are also available in `company/amazon/`, `company/facebook/`, `company/linkedin/`, `company/twitter/`, and other directories within the repository.