Leetcode 235: Lowest Common Ancestor of a Binary Search Tree
grid47 Exploring patterns and algorithms
Oct 14, 2024
6 min read
Solution to LeetCode 235: Lowest Common Ancestor of a Binary Search Tree Problem
Given a Binary Search Tree (BST), find the lowest common ancestor (LCA) of two given nodes. The lowest common ancestor is the deepest node that is an ancestor of both nodes. An ancestor of a node is a node itself or any node in its path up to the root.
Problem
Approach
Steps
Complexity
Input: The input consists of the root node of the binary search tree and two target nodes p and q.
• The number of nodes in the tree is between 2 and 10^5.
• Node values are unique.
• The values of p and q are distinct, and both p and q are guaranteed to exist in the tree.
Output: The output should be the node that represents the lowest common ancestor of nodes p and q.
Example: Output: 3
Constraints:
Goal: Find the lowest common ancestor (LCA) in a binary search tree by leveraging the BST property that the left child is smaller and the right child is greater.
Steps:
• If the current node's value is less than both p and q, move to the right subtree.
• If the current node's value is greater than both p and q, move to the left subtree.
• If one of the nodes is smaller and the other is larger, the current node is the LCA.
Goal: Ensure that the solution works within the constraints of a binary search tree and that the nodes p and q exist in the tree.
Steps:
Assumptions:
• The tree is a valid binary search tree.
• The nodes p and q are distinct and guaranteed to exist in the tree.
• Explanation: In this tree, the LCA of nodes 2 and 8 is 6, as 6 is the ancestor of both 2 and 8.
Approach: We can solve this problem efficiently using the properties of the Binary Search Tree. Starting from the root, we compare the values of the nodes p and q with the current node's value and decide whether to move left or right.
Observations:
• A Binary Search Tree (BST) allows us to quickly decide whether to move to the left or right subtree based on the node values.
• The problem becomes easier because we know that for any node, all values in its left subtree are smaller, and all values in its right subtree are larger.
• We need to find the first node that satisfies the condition where one of the nodes is smaller and the other is larger, or if one of the nodes is the current node itself.
Steps:
• Start from the root node of the BST.
• If both p and q are smaller than the current node, move to the left subtree.
• If both p and q are larger than the current node, move to the right subtree.
• If one node is smaller and the other is larger, the current node is the LCA.
Empty Inputs:
• The tree will not be empty, as p and q are guaranteed to exist.
Large Inputs:
• Ensure that the solution efficiently handles trees with up to 10^5 nodes.
Special Values:
• If one of the nodes is the root, it will be the LCA if the other node is its descendant.
Constraints:
• The solution must be efficient, ideally with a time complexity of O(log n) in a balanced BST.
Defines the `lowestCommonAncestor` function, which takes the root node of the BST and two target nodes (`p` and `q`) as input and returns the lowest common ancestor.
2 : Left Subtree Check
if(root->val < p->val && root->val < q->val)
Checks if both target nodes (`p` and `q`) are located in the right subtree of the current node (`root`). If so, the function recursively calls itself on the right child of `root`.
3 : Right Subtree Check
returnlowestCommonAncestor(root->right, p, q);
Recursively calls `lowestCommonAncestor` on the right subtree of `root` if both `p` and `q` are greater than `root`.
4 : Right Subtree Check (Alternative)
if(root->val > p->val && root->val > q->val)
Checks if both target nodes (`p` and `q`) are located in the left subtree of the current node (`root`). If so, the function recursively calls itself on the left child of `root`.
5 : Left Subtree Check (Alternative)
returnlowestCommonAncestor(root->left, p, q);
Recursively calls `lowestCommonAncestor` on the left subtree of `root` if both `p` and `q` are smaller than `root`.
6 : Ancestor Return
return root;
Returns `root` when the current node is the lowest common ancestor, meaning one node is in the left subtree and the other is in the right, or one of the nodes is `root` itself.
Best Case: O(log n) in a balanced BST, where n is the number of nodes.
Average Case: O(log n), assuming the tree is balanced.
Worst Case: O(n) in the case of a skewed tree (e.g., a degenerate tree resembling a linked list).
Description: The time complexity depends on the height of the tree, which can be log n for a balanced BST.
Best Case: O(1), if we use an iterative approach instead of recursion.
Worst Case: O(h), where h is the height of the tree (due to recursion).
Description: The space complexity is proportional to the height of the tree due to the recursion stack.
