> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Lowest Common Ancestor of a Binary Tree III

> Tested Python solution for LeetCode 1650 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 1650, [Medium](/catalog/medium). Topics: [Tree](/catalog/topics/tree), [Hash Table](/catalog/topics/hash-table), [Two Pointers](/catalog/topics/two-pointers), [Binary Tree](/catalog/topics/binary-tree), Lowest Common Ancestor. [View on LeetCode](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1650   # by problem number
lcpy gen -s lowest_common_ancestor_of_a_binary_tree_iii   # by problem name
```

## Problem

Given two nodes of a binary tree `p` and `q`, return *their* *lowest common ancestor (LCA)*.

Each node will have a reference to its parent node. The definition for `Node` is below:

```
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}
```

According to the **definition of LCA on Wikipedia**: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

### Examples

![Example 1](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1600-1699/1650.Lowest%20Common%20Ancestor%20of%20a%20Binary%20Tree%20III/images/binarytree.png)

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

![Example 2](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1600-1699/1650.Lowest%20Common%20Ancestor%20of%20a%20Binary%20Tree%20III/images/binarytree.png)

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

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

### Constraints

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

**Follow up:** Can you find the LCA without using any extra space (excluding recursion) and without knowing the root of the tree?

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/lowest_common_ancestor_of_a_binary_tree_iii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/lowest_common_ancestor_of_a_binary_tree_iii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from __future__ import annotations


class Node:
    def __init__(self, val: int = 0) -> None:
        self.val = val
        self.left: Node | None = None
        self.right: Node | None = None
        self.parent: Node | None = None


class Solution:
    # Time: O(h) where h is the height of the tree
    # Space: O(1)
    def lowest_common_ancestor(self, p: Node, q: Node) -> Node:
        a: Node | None = p
        b: Node | None = q
        while a is not b:
            a = q if a.parent is None else a.parent
            b = p if b.parent is None else b.parent
        assert a is not None
        return a
```

## Complexity

| Time | Space |
| - | - |
| O(h) where h is the height of the tree | O(1) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.