Lowest Common Ancestor of a Binary Tree
Finding the lowest common ancestor (LCA) in a binary tree (not necessarily a BST) is a bit more complex since the tree doesn’t have the sorted order property of a BST.
A recursive approach can be used to solve this problem. Here’s how it works:
Base Case: If the root is null, return null. If the root’s value is equal to either
p
orq
, return the root.Search Left and Right Subtrees: Recursively call the function on the left and right children of the root.
Analyze the Results:
- If both left and right calls return a non-null value, then the current root is the LCA.
- If only one of the left or right calls returns a non-null value, return that value.
- If both return null, return null.
The code below implements this approach:
|
|
Here’s a breakdown of how it works:
- The base case returns the current root if it’s equal to
p
orq
, or if it’s null. - It then calls itself on the left and right children of the root, storing the results.
- It analyzes the results to determine the LCA and returns it.
This solution is efficient, with a time complexity of O(n), where n is the number of nodes in the tree.