Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
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 = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [2,1], p = 2, q = 1 Output: 2
Constraints:
[2, 105].-109 <= Node.val <= 109Node.val are unique.p != qp and q will exist in the BST.This method exploits the properties of a BST. The idea is to traverse the tree starting from the root. If both p and q are greater than the current node, then the LCA lies in the right subtree. If both are smaller, then it lies in the left subtree. Otherwise, the current node is the LCA.
This C code implements the recursive approach by checking if both nodes' values are either greater or less than the current node. If so, recursively proceed to the right or left subtree, respectively. Otherwise, return the current node as the LCA.
C++
Java
Python
C#
JavaScript
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to the recursion stack.
Instead of recursion, this method uses a while loop to traverse the tree. Starting from the root, check if both nodes are greater or smaller than the current node to decide whether to proceed to the right or left subtree respectively. If neither, we've found the LCA.
This C implementation uses an iterative approach via a loop to find the LCA. It makes use of BST properties to decide movement between left and right nodes.
C++
Java
Python
C#
JavaScript
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(1) since it does not use extra space beyond variables.
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(h), where h is the height of the tree. |
| Iterative Approach | Time Complexity: O(h), where h is the height of the tree. |
L27. Lowest Common Ancestor in Binary Tree | LCA | C++ | Java • take U forward • 379,697 views views
Watch 9 more video solutions →Practice Lowest Common Ancestor of a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor