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 nonnull value, then the current root is the LCA.
 If only one of the left or right calls returns a nonnull 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.