Given a binary tree and two nodes (p and q), find their lowest common ancestor (LCA). The LCA of two nodes p and q in a binary tree is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).
Lowest Common Ancestor (LCA) in a Binary Tree - Algorithm and Code Examples
Problem Statement
Examples
Solution
Algorithm Steps
Code
C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left, *right;
} TreeNode;
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = node->right = NULL;
return node;
}
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);
if (left && right) return root;
return left ? left : right;
}
int main() {
TreeNode* root = createNode(3);
root->left = createNode(5);
root->right = createNode(1);
root->left->left = createNode(6);
root->left->right = createNode(2);
root->right->left = createNode(0);
root->right->right = createNode(8);
root->left->right->left = createNode(7);
root->left->right->right = createNode(4);
TreeNode* lca = lowestCommonAncestor(root, root->left->right->left, root->left->right->right);
printf("LCA: %d\n", lca ? lca->val : -1);
return 0;
}
Problem Statement
Examples
Solution
Algorithm Steps
Code
C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left, *right;
} TreeNode;
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = node->right = NULL;
return node;
}
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);
if (left && right) return root;
return left ? left : right;
}
int main() {
TreeNode* root = createNode(3);
root->left = createNode(5);
root->right = createNode(1);
root->left->left = createNode(6);
root->left->right = createNode(2);
root->right->left = createNode(0);
root->right->right = createNode(8);
root->left->right->left = createNode(7);
root->left->right->right = createNode(4);
TreeNode* lca = lowestCommonAncestor(root, root->left->right->left, root->left->right->right);
printf("LCA: %d\n", lca ? lca->val : -1);
return 0;
}
Comments
Loading comments...