Sponsored
Sponsored
This approach uses recursion to traverse the tree starting from the root. If the current node is either p or q, then the node is returned upwards in the recursion stack as the potential LCA. Otherwise, we continue to search both left and right subtrees. If both subtrees return non-null values, it means p and q are in different subtrees, and the current node is the LCA. If only one subtree returns a non-null value, it means both nodes are located in that subtree and that subtree's root should be the LCA.
Time Complexity: O(N), where N is the number of nodes in the binary tree, as we visit each node only once.
Space Complexity: O(N) due to the recursion stack when the tree is completely unbalanced.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode
This C code defines a recursive function to find the LCA of two nodes in a binary tree. It checks if the current node is NULL or matches either of the two nodes p or q and returns the node if true. It then recursively checks the left and right children. If both are non-null, the current node is the LCA; otherwise, it returns the non-null child.
The basic idea is to find the paths from the root to the two nodes p and q. Once you have the paths, compare them to find the deepest common node. This method is straightforward, using known operations to reconfirm ancestor status along determined paths.
Time Complexity: O(N) due to double traversal in finding paths for each node.
Space Complexity: O(H), where H is the height of the tree for storing path information.
In JavaScript, this implementation builds full root-to-target paths in arrays, using them to identify the last shared element as the lowest common ancestor.