Algorithm

Problem Name: 236. Lowest Common Ancestor of a Binary Tree

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
```

Constraints:

• The number of nodes in the tree is in the range `[2, 105]`.
• `-109 <= Node.val <= 109`
• All `Node.val` are unique.
• `p != q`
• `p` and `q` will exist in the tree.

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
int match(struct TreeNode *node, struct TreeNode *n) {
if (!node) return 0;
return (node == n || match(node->left, n) || match(node->right, n)) ? 1 : 0;
}
struct TreeNode *traversal(struct TreeNode *node, struct TreeNode *p, struct TreeNode *q) {
struct TreeNode *lca;

// post order traversal
if (node->left) {
lca = traversal(node->left, p, q);
if (lca) return lca;
}

if (node->right) {
lca = traversal(node->right, p, q);
if (lca) return lca;
}

if (node == p && (match(node->left, q) || match(node->right, q))) return node;

if (match(node->left, p) && match(node->right, q)) return node;

return NULL;
}
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
struct TreeNode *node;

node = traversal(root, p, q);
if (!node) node = traversal(root, q, p);

return node;
}
``````
Copy The Code &

Input

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

Output

cmd
3

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
bool foundP = found(root->left, p);
bool foundQ = found(root->right, q);
if (foundP && foundQ || !foundP && !foundQ) return root;
if (foundP) return lowestCommonAncestor(root->left, p, q);
return lowestCommonAncestor(root->right, p, q);
}

bool found(TreeNode* root, TreeNode* target) {
if (!root) return false;
if (root == target) return true;
return found(root->left, target) || found(root->right, target);
}
};
``````
Copy The Code &

Input

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

Output

cmd
3

#3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode leftRoot = lowestCommonAncestor(root.left, p, q);
TreeNode rightRoot = lowestCommonAncestor(root.right, p, q);
if (leftRoot != null && rightRoot != null) {
return root;
}
return leftRoot != null ? leftRoot : rightRoot;
}
}
``````
Copy The Code &

Input

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

Output

cmd
5

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const lowestCommonAncestor = function(root, p, q) {
const arr = []
traverse(root, [], arr)
let pii
let qii
// in same path
for(let i = 0; i  <  arr.length; i++) {
let pi = arr[i].indexOf(p.val)
let qi = arr[i].indexOf(q.val)
if(pi !== -1) pii = [i, pi]
if(qi !== -1) qii = [i, qi]
if(pi !== -1 && qi !== -1) {
return new TreeNode( pi <= qi ? p.val : q.val )
}
}

const len = Math.min(arr[pii[0]].length, arr[qii[0]].length)
const pp = arr[pii[0]]
const qp = arr[qii[0]]
for(let i = 0; i  <  len; i++) {
if(pp[i] !== qp[i]) return new TreeNode(pp[i - 1])
}
};

function traverse(node, path = [], arr) {
if(node == null) return
path.push(node.val)
if(node.left === null && node.right === null) {
arr.push(path.slice(0))
return
}
traverse(node.left, path.slice(0), arr)
traverse(node.right, path.slice(0), arr>
}
``````
Copy The Code &

Input

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

Output

cmd
5

#5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def lowestCommonAncestor(
self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
) -> "TreeNode":
parent, stack = {root: None}, [root]
while p not in parent or q not in parent:
node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
ancestors = set()
while p:
p = parent[p]
while q not in ancestors:
q = parent[q]
return q
``````
Copy The Code &

Input

cmd
root = [1,2], p = 1, q = 2

Output

cmd
1

#6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0236_LowestCommonAncestorOfABinaryTree
{
private TreeNode result;

public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
Find(root, p, q);
return result;
}

public bool Find(TreeNode root, TreeNode p, TreeNode q)
{
if (root == null) return false;

var left = Find(root.left, p, q) ? 1 : 0;
var right = Find(root.right, p, q) ? 1 : 0;
var self = (root == p || root == q) ? 1 : 0;

if (left + right + self >= 2) result = root;
return left + right + self > 0;
}
}
}
``````
Copy The Code &

Input

cmd
root = [1,2], p = 1, q = 2

Output

cmd
1