Last updated on January 5th, 2025 at 12:38 am
Here, we see the Lowest Common Ancestor of a Binary Tree LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Tree
Companies
Amazon, Apple, Facebook, LinkedIn, Microsoft
Level of Question
Medium
Lowest Common Ancestor of a Binary Tree LeetCode Solution
Table of Contents
1. Problem Statement
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
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 = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
2. Coding Pattern Used in Solution
The coding pattern used in this code is Tree Depth First Search (DFS). The algorithm traverses the binary tree recursively, exploring each branch of the tree until it finds the nodes p and q or reaches a leaf node. This is a classic DFS approach applied to trees.
3. Code Implementation in Different Languages
3.1 Lowest Common Ancestor of a Binary Tree C++
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
return !left ? right : !right ? left : root;
}
};
3.2 Lowest Common Ancestor of a Binary Tree Java
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
return left == null ? right : right == null ? left : root;
}
}
3.3 Lowest Common Ancestor of a Binary Tree JavaScript
var lowestCommonAncestor = function(root, p, q) {
if (!root || root === p || root === q) return root;
var resL = lowestCommonAncestor(root.left, p, q);
var resR = lowestCommonAncestor(root.right, p, q);
return (resL && resR) ? root : (resL || resR);
};
3.4 Lowest Common Ancestor of a Binary Tree Python
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
if root in (None, p, q): return root
subs = [self.lowestCommonAncestor(kid, p, q)
for kid in (root.left, root.right)]
return root if all(subs) else max(subs)
4. Time and Space Complexity
| Time Complexity | Space Complexity(Balanced Tree) | Space Complexity(Unbalanced Tree) | |
| C++ | O(N) | O(log(N)) | O(N) |
| Java | O(N) | O(log(N)) | O(N) |
| JavaScript | O(N) | O(log(N)) | O(N) |
| Python | O(N) | O(log(N)) | O(N) |
- The code is functionally identical across all four languages, with only syntactic differences.
- The recursive approach is elegant and concise but can lead to stack overflow for very deep trees. An iterative approach could be used to mitigate this in practice.
- The algorithm assumes that both
pandqexist in the tree. If this assumption is not guaranteed, additional checks may be needed.