# 🤖 leetcode 236. Lowest Common Ancestor of a Binary Tree | medium | tree | javascript

## 🗒️ Problems

Lowest Common Ancestor of a Binary Tree - LeetCode

``````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).”
``````

## 🤔 First attempt

At first, I just tried the procedure approach.

• From the one node, find `ancestor` until the root.
• From the another node, find the common node among previously found ancestors from that node to the root.
``````var lowestCommonAncestor = function (root, p, q) {
const dfs = (node, parent) => {
if (!node) return;

node.parent = parent;

dfs(node.left, node);
dfs(node.right, node);
};

dfs(root, null);

const ancestors = new Set();

while (p) {
p = p.parent;
}

while (!ancestors.has(q)) {
q = q.parent;
}

return q;
};
``````

## ✨ Idea

• Let's think about the recursive way.
• Especially ⬆️ bottom-up postorder traversal.

## 🍀 Intuition

### 🌲💡 Recursive way : ⬆️ bottom-up postorder traversal

``````const left = dfs(node.left, p, q);
const right = dfs(node.right, p, q);

// post-order
``````

Can you proceed further based on the result ?

• the result of the children nodes : left, right
• current node.

## basecase

• If the node is null, just return null.
``````const dfs = (node, p, q) => {
if (!node) return null;
};
``````
• If the current node is matching either the given two reference nodes, just return the current node.
``````if (node === p || node === q) return node;
``````

## 💡🌲 Case #1 : If the both [object Object] and [object Object] are found.

• If the both of `left` and `right` nodes are found, this means that this node is LCA.
• Now we are using post-order recursion.
• Therefore the first node which finds these both `left` and `right` will be LCA.
``````if (left && right) return node;
``````

## 💡🌲 Case #2 : If none of [object Object] and [object Object] are found.

• If the none of the `left` and `right` nodes are found, there is no LCA.
``````if (!left && !right) return null;
``````

## 💡🌲 Case #3 : If only either [object Object] or [object Object] is found

• If only one of `left` and `right` is found, that node is LCA.
``````if (left || right) return left || right;
``````

## 🔥🌲 My Solution

``````/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
const dfs = (node, p, q) => {
if (!node) return null;

if (node === p || node === q) return node;

const left = dfs(node.left, p, q);
const right = dfs(node.right, p, q);

if (left && right) return node;
if (!left && !right) return null;
if (left || right) return left || right;
};

return dfs(root, p, q);
};
``````