Lowest Common Ancestor of a Binary Search Tree

🇷🇺 Название: Наименьший общий предок дерева бинарного поиска
LeetCode: lowest-common-ancestor-of-a-binary-search-tree
Временная сложность: O(h)
Пространственная сложность: O(1)

Решение

# Definition for a binary tree node.  
# class TreeNode:  
#     def __init__(self, x):  
#         self.val = x  
#         self.left = None  
#         self.right = None  


class Solution:  
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':  
        small = min(p.val, q.val)  
        large = max(p.val, q.val)  

        while root:  
            if root.val > large:  
                root = root.left  
            elif root.val < small:  
                root = root.right  
            else:  
                return root  
        return None

🇺🇸 Условие

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

🇷🇺 Условие

Примеры

Example 1:


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:


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

{
  "examples": [
    {
      "input": {
        "root": [6,2,8,0,4,7,9,null,null,3,5],
        "p": 2,
        "q": 8
      },
      "output": 6
    },
    {
      "input": {
        "root": [6,2,8,0,4,7,9,null,null,3,5],
        "p": 2,
        "q": 4
      },
      "output": 2
    },
    {
      "input": {
        "root": [2,1],
        "p": 2,
        "q": 1
      },
      "output": 2
    }
  ]
}

Ограничения

• The number of nodes in the tree is in the range \([2, 10^5]\).
• \(-10^9 \leq Node.val \leq 10^9\)
• All Node.val are unique.
• p != q
• p and q will exist in the BST.

Потребление ресурсов

⏱ Time complexity: O(h)

• В каждом шаге переходим либо влево, либо вправо — как в обычном поиске в BST.
• Этот алгоритм работает только для BST (двоичного дерева поиска).
• h — высота дерева:
  • в среднем O(log n) (сбалансированное дерево),
  • в худшем O(n) (вырожденное дерево — список).

Итог: O(h)

🧠 Space complexity: O(1)

• Используется только один указатель root, меняющийся на месте.
• Нет рекурсии, нет стека, нет дополнительных структур.

Итог: O(1)

medium tree depth-first-search binary-search-tree binary-tree

---

Metadata

• title_rus: Наименьший общий предок дерева бинарного поиска
• difficulty: Medium
• leetcode_url: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
• topics: ['Tree', 'Depth-First Search', 'Binary Search Tree', 'Binary Tree']
• time: O(h)
• space: O(1)
• grind75: True
• tags: ['Binary Search Tree', 'Binary Tree', 'Depth-First Search', 'Medium', 'Tree', 'problem']
• git_revision_date_localized: 5 июля 2025 г.
• git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_revision_date_localized_tag:
• git_revision_date_localized_raw_date: 5 июля 2025 г.
• git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_revision_date_localized_raw_iso_date: 2025-07-05
• git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_revision_date_localized_raw_timeago:
• git_revision_date_localized_raw_custom: 05. июля 2025
• git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_site_revision_date_localized_tag:
• git_site_revision_date_localized: 5 июля 2025 г.
• git_site_revision_date_localized_raw_date: 5 июля 2025 г.
• git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_site_revision_date_localized_raw_iso_date: 2025-07-05
• git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_site_revision_date_localized_raw_timeago:
• git_site_revision_date_localized_raw_custom: 05. июля 2025