236. Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree (LeetCode 236) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Lowest Common Ancestor (LCA) Finding subpattern.

How to solve Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree is a Lowest Common Ancestor problem, part of Tree Traversal Patterns (DFS & BFS). Find lowest common ancestor in binary trees and BSTs using recursive and iterative approaches.

Work towards the solution in these steps:

1. Consider using a tree traversal technique like Depth-First Search (DFS) to explore nodes systematically.
2. Think about how recursion can help you check whether the current node is an ancestor of either target node.
3. When traversing, determine if the current node matches either target node or if those nodes are found in different subtrees.

The reference solution runs in O(N) time and O(N) space.

The Lowest Common Ancestor of a Binary Tree solution and editorial walks through the full approach with reference code.

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,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, 105].

- -109 <= Node.val <= 109

- All Node.val are unique.

- p != q

- p and q will exist in the tree.

Topics and companies

Topics: Tree, Depth-First Search, Binary Tree.

Reported in interviews at Facebook, Microsoft, Amazon, Oracle, LinkedIn, Apple, Bloomberg, Intuit, Adobe, Google, Uber, Zillow and others.

How to practise Lowest Common Ancestor of a Binary Tree on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N) time and O(N) space.

Open Lowest Common Ancestor of a Binary Tree in the code editor, or read the Lowest Common Ancestor of a Binary Tree editorial for a worked solution with its approach and complexity analysis.

Where Lowest Common Ancestor of a Binary Tree sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Lowest Common Ancestor (LCA) Finding subpattern
• The full DSA patterns sheet

Problems related to Lowest Common Ancestor of a Binary Tree

Other problems that use the same Lowest Common Ancestor (LCA) Finding and Tree Traversal Patterns (DFS & BFS) techniques:

• Lowest Common Ancestor of a Binary Search Tree — Medium, same subpattern
• All Nodes Distance K in Binary Tree — Medium, same pattern
• Balanced Binary Tree — Easy, same pattern
• Binary Search Tree Iterator — Medium, same pattern
• Binary Tree Inorder Traversal — Easy, same pattern
• Binary Tree Level Order Traversal — Medium, same pattern

Lowest Common Ancestor of a Binary Tree FAQ