Find the lowest common ancestor of a binary tree.
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The LCA is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: Node 4 is a direct descendant of Node 5 in the tree, making Node 5 the lowest common ancestor of both.

Question

Find the lowest common ancestor of a binary tree.

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The LCA is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants.

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: 5

Explanation: Node 4 is a direct descendant of Node 5 in the tree, making Node 5 the lowest common ancestor of both.

Anonymous · Accepted Answer

TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q){

if(!root) return root;

if(root == p || root == q) return root;
TreeNode* left = lca(root->left, p, q);

TreeNode* right = lca(root->right, p, q);

if(left && right) return root;

return left? left : right;

}

Find the lowest common ancestor of a binary tree.

Practice this question with AI

Go Premium

Community Answers

Unlock Full Access

Practice More Questions