:orphan:

Lowest Common Ancestor of a BST
===============================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

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 <https://en.wikipedia.org/wiki/Lowest_common_ancestor>`__:
“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**).”

 

**Example 1:**

|image1|

::


   Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
   Output: 6
   Explanation: The LCA of nodes 2 and 8 is 6.

**Example 2:**

|image2|

::


   Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
   Output: 2
   Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

**Example 3:**

::


   Input: root = [2,1], p = 2, q = 1
   Output: 2

 

**Constraints:**

- The number of nodes in the tree is in the range
  ``[2, 10``\ :sup:```5```\ ``]``.
- ``-10``\ :sup:```9```\ ``<= Node.val <= 10``\ :sup:```9```
- All ``Node.val`` are **unique**.
- ``p != q``
- ``p`` and ``q`` will exist in the BST.

.. |image1| image:: https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png
.. |image2| image:: https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png

.. highlight:: python

Pattern
-------
Tree, Depth-First Search, Binary Search Tree, Binary Tree

Approaches
----------

.. tab-set::

    .. tab-item:: Recursive

        **Code**

        .. literalinclude:: ../problems/medium/lowest-common-ancestor-of-a-binary-search-tree/lowest_common_ancestor_of_a_binary_search_tree__recursive.py
            :language: python
            :lines: 10-

        **Test**

        >>> from lowest_common_ancestor_of_a_binary_search_tree__recursive import lowestCommonAncestor, TreeNode
        >>> root = TreeNode.from_list([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])
        >>> lowestCommonAncestor(root, TreeNode(2), TreeNode(8)).val
        6
        >>> lowestCommonAncestor(root, TreeNode(2), TreeNode(4)).val
        2

        .. autoclass:: lowest_common_ancestor_of_a_binary_search_tree__recursive.TreeNode
           :members:
           :show-inheritance:
           :undoc-members:

        .. autofunction:: lowest_common_ancestor_of_a_binary_search_tree__recursive.lowestCommonAncestor