Find the lowest common ancestor (LCA) of two nodes in a binary tree.

Our solution for finding the Lowest Common Ancestor (LCA) of two nodes in a binary tree follows a recursive approach. At each node, we check if either of the two nodes (p or q) is the current node. If the current node matches one of the target nodes, we return the current node as a potential LCA.

Next, we recursively traverse the left and right subtrees of the current node. The recursion returns the LCA found in the left subtree and the LCA found in the right subtree.

• If both left and right recursive calls return non-null values, it means that one node (p or q) was found in the left subtree and the other was found in the right subtree. Therefore, the current node is the LCA of p and q.
• If only one of the left or right calls returns a non-null value, it means both nodes are in the same subtree, and the non-null return value is the LCA.
• If both left and right calls return null, we return null to indicate that neither p nor q is found in this subtree.

This recursive process continues until the lowest node that has both p and q as descendants is found.

Time Complexity: The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because in the worst case, the algorithm visits every node once.

Space Complexity: The space complexity is O(h), where h is the height of the tree. This space is used for the recursive call stack. In the worst case of a completely unbalanced tree, this could be O(n), while in a balanced tree, it would be O(log n).