Leetcode 236: Lowest Common Ancestor of a Binary Tree
grid47 Exploring patterns and algorithms
Oct 14, 2024
5 min read
Solution to LeetCode 236: Lowest Common Ancestor of a Binary Tree Problem
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes. The lowest common ancestor is defined as the lowest node that is an ancestor of both nodes p and q. A node can be a descendant of itself.
Problem
Approach
Steps
Complexity
Input: The input consists of the root of the binary tree and two nodes, p and q, whose lowest common ancestor is to be found.
• Explanation: In this tree, the LCA of nodes 5 and 4 is 5, as 5 is the ancestor of node 4.
Approach: The problem can be solved using a recursive approach to find the lowest common ancestor in a binary tree by checking the presence of nodes p and q in the left and right subtrees.
Observations:
• The binary tree structure allows us to search in both the left and right subtrees for the target nodes.
• We can use recursion to traverse the tree and identify the common ancestor.
• The key observation is that the LCA is found where one node is in the left subtree, and the other is in the right subtree, or when one of the nodes is the current node.
Steps:
• Check if the current node is null. If so, return null.
• If the current node is p or q, return that node.
• Recursively search for p and q in the left subtree.
• Recursively search for p and q in the right subtree.
• If both left and right subtrees return non-null values, the current node is the LCA.
• If only one of the subtrees returns a non-null value, return that value.
Empty Inputs:
• The tree cannot be empty, as both p and q must exist in the tree.
Large Inputs:
• Ensure that the solution can handle trees with up to 10^5 nodes efficiently.
Special Values:
• If one of the nodes is the root node, the root itself is the LCA if the other node is in its subtree.
Constraints:
• The solution should be efficient and handle the recursion stack well for large inputs.
Defines the `lowestCommonAncestor` function, which takes the root of the tree and two target nodes (`p` and `q`) as input and returns their lowest common ancestor.
2 : Base Case Check
if(!root || root == p || root == q) return root;
Checks for the base case: if the root is `null`, or if the root is one of the target nodes (`p` or `q`), then it returns the root as the lowest common ancestor.
3 : Left Subtree Search
TreeNode* left = lowestCommonAncestor(root->left, p, q);
Recursively calls `lowestCommonAncestor` on the left subtree of the current root. It searches for the common ancestor in the left subtree.
4 : Right Subtree Search
TreeNode* right = lowestCommonAncestor(root->right, p, q);
Recursively calls `lowestCommonAncestor` on the right subtree of the current root. It searches for the common ancestor in the right subtree.
5 : Return Result
return!left?right: !right?left : root;
If one of the subtrees is `null`, it returns the non-null subtree (either `left` or `right`). If both subtrees are non-null, it means the current root is the lowest common ancestor, so it returns `root`.
Best Case: O(log n) for a balanced tree, where n is the number of nodes.
Average Case: O(log n) assuming the tree is balanced.
Worst Case: O(n) for a skewed tree, where n is the number of nodes.
Description: The time complexity is determined by the depth of the tree, which can be log n for a balanced tree or n for a skewed tree.
Best Case: O(1) if we use an iterative approach.
Worst Case: O(h), where h is the height of the tree (due to recursion stack).
Description: The space complexity depends on the height of the tree because of the recursion stack.
