Tree/lowest_common_ancestor library

🌳 Lowest Common Ancestor (LCA)

Finds the lowest common ancestor of two nodes in a binary tree. The LCA is the deepest node that has both nodes as descendants. Returns null if either node is not present in the tree.

Time complexity: O(n) where n is the number of nodes Space complexity: O(h) where h is the height of the tree (worst case O(n))

Example:

final root = BinaryTreeNode<int>(10);
root.left = BinaryTreeNode<int>(5);
root.right = BinaryTreeNode<int>(15);
root.left!.left = BinaryTreeNode<int>(3);
root.left!.right = BinaryTreeNode<int>(7);
final lca = lowestCommonAncestor(root, 3, 7);
// lca.value: 5

Functions

lowestCommonAncestor<T>(BinaryTreeNode<T>? root, T p, T q) → BinaryTreeNode<T>?

Returns the lowest common ancestor node of values p and q in the binary tree rooted at root. Returns null if either p or q is not present in the tree.