Leetcode - Lowest Common Ancestor of a Binary Search Tree

Question

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

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

This is atree question.

Idea(s)

• Use the structure of a BST to search for LCA (smaller numbers on the left, larger numbers on the right)
• The LCA is where the “split” occurs (the first node where p and q are in different subtrees)
• The LCA could also be p or q so we need to check if our current node is p or q, and then check if the other is a child of our current node
• This essentially boils down to:
  • Is p and q > than our current node? Go to the right
  • Is p and q < than our current node? Go to the left
  • Otherwise, we have a split case, or one of the values is equal to our current node, return the value of that node since that is our results (these are our two LCA conditions)

Solution