lowestCommonAncestor<T> function

BinaryTreeNode<T>? lowestCommonAncestor<T>(
  1. BinaryTreeNode<T>? root,
  2. T p,
  3. T q
)

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.

Implementation

BinaryTreeNode<T>? lowestCommonAncestor<T>(BinaryTreeNode<T>? root, T p, T q) {
  if (root == null) return null;

  final pExists = _containsValue(root, p);
  final qExists = _containsValue(root, q);
  if (!pExists && !qExists) return null;
  if (!pExists) return _findNode(root, q);
  if (!qExists) return _findNode(root, p);

  return _lcaHelper(root, p, q);
}