Binary Tree Lowest Common Ancestor¶
Table of Contents¶
- 235. Lowest Common Ancestor of a Binary Search Tree (Medium)
- 236. Lowest Common Ancestor of a Binary Tree (Medium)
- 1123. Lowest Common Ancestor of Deepest Leaves (Medium)
- 2096. Step-By-Step Directions From a Binary Tree Node to Another (Medium)
- 1740. Find Distance in a Binary Tree (Medium) 👑
- 1644. Lowest Common Ancestor of a Binary Tree II (Medium) 👑
- 1650. Lowest Common Ancestor of a Binary Tree III (Medium) 👑
- 1676. Lowest Common Ancestor of a Binary Tree IV (Medium) 👑
235. Lowest Common Ancestor of a Binary Search Tree¶
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def lowestCommonAncestor(root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
while root:
if root.val > p.val and root.val > q.val:
root = root.left
elif root.val < p.val and root.val < q.val:
root = root.right
else:
return root
root = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]
root = build(root)
p = root.left
q = root.right
print(root)
# ______6__
# / \
# 2__ 8
# / \ / \
# 0 4 7 9
# / \
# 3 5
print(lowestCommonAncestor(root, p, q))
# ______6__
# / \
# 2__ 8
# / \ / \
# 0 4 7 9
# / \
# 3 5
236. Lowest Common Ancestor of a Binary Tree¶
from typing import List, Optional
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class LowestCommonAncestor:
def lowestCommonAncestor(
self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
) -> "TreeNode":
if not root or q == root or p == root:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right
if __name__ == "__main__":
root = build([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
print(root)
# ______3__
# / \
# 5__ 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
p = root.left # 5
q = root.right # 1
sol = LowestCommonAncestor()
print(sol.lowestCommonAncestor(root, p, q))
# ______3__
# / \
# 5__ 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right)
: val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || 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() { return 0; }
1123. Lowest Common Ancestor of Deepest Leaves¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Lowest Common Ancestor
def lcaDeepestLeaves(root: Optional[TreeNode]) -> Optional[TreeNode]:
res = None
max_depth = -1
def dfs(node, depth) -> int:
nonlocal res, max_depth
if not node:
max_depth = max(max_depth, depth)
return depth
left_max_depth = dfs(node.left, depth + 1)
right_max_depth = dfs(node.right, depth + 1)
if left_max_depth == right_max_depth == max_depth:
res = node
return max(left_max_depth, right_max_depth)
dfs(root, 0)
return res
if __name__ == "__main__":
root = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]
root = build(root)
print(root)
# ______3__
# / \
# 5__ 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
print(lcaDeepestLeaves(root)) # 2
# 2
# / \
# 7 4
2096. Step-By-Step Directions From a Binary Tree Node to Another¶
from typing import Optional
from binarytree import Node as TreeNode
class GetDirections:
def lca(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
path_s, path_t = [], []
def dfs(node, target, path):
if not node:
return False
if node.val == target:
return True
path.append("L")
if dfs(node.left, target, path):
return True
path.pop()
path.append("R")
if dfs(node.right, target, path):
return True
path.pop()
return False
dfs(root, startValue, path_s)
dfs(root, destValue, path_t)
i = 0
while i < len(path_s) and i < len(path_t) and path_s[i] == path_t[i]:
i += 1
UP = "U" * (len(path_s) - i)
DOWN = "".join(path_t[i:])
return UP + DOWN
1740. Find Distance in a Binary Tree 👑¶
from typing import Optional
from binarytree import Node as TreeNode
class Solution:
def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:
LCA = self.find_LCA(root, p, q) # Least Common Ancestor
p_dep = self.dfs(LCA, p)
q_dep = self.dfs(LCA, q)
return p_dep + q_dep
def dfs(self, root: TreeNode, target: int) -> int:
"""Depth of target node from node"""
if not root:
return -1
if root.val == target:
return 0
L = self.dfs(root.left, target)
R = self.dfs(root.right, target)
if L == -1 and R == -1:
return -1
return max(L, R) + 1
def find_LCA(self, root: TreeNode, p: int, q: int) -> TreeNode:
if not root or root.val == p or root.val == q:
return root
L = self.find_LCA(root.left, p, q)
R = self.find_LCA(root.right, p, q)
if L and R:
return root
elif L and not R:
return L
elif not L and R:
return R
else:
return None