Lowest Common Ancestor in a Binary Tree

January 6, 2024

Problem # Given a binary tree (not a binary search tree) and two nodes values, find the lowest common ancestor (LCA) of the two nodes in the tree. The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself). Example # Input: Root of the Binary Tree, p = 5, q = 1 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3. ...