# 236 Lowest Common Ancestor of a Binary Tree

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

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 v and w as the lowest node in T that has both v and w as descendants (where we allow **a node to be a descendant of itself**).”

```
        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
```

For example, the lowest common ancestor (LCA) of nodes`5`and`1`is`3`. Another example is LCA of nodes`5`and`4`is`5`, since a node can be a descendant of itself according to the LCA definition.

**The Idea:** We know that the lowest common ancestor will intersect in paths as we iterate from both nodes towards the root of the tree. I am reminded of the problem that identifies the intersection two linked lists. Since one path can be longer than the other, with the linked lists, what we can do is find out the lengths of both linked lists and iterate the longer linked list the difference of the lengths. This way when we iterate both linked lists together, they will be the same length, and the intersection of paths will be when the iterators are the same value.

The same idea is found here, but instead, we build two paths. One to node a, and a second path to node b. Then, we begin iterating backwards from the smaller length path until we find a match (same as the linked lists). Since we know both paths cannot be empty, and the highest common ancestor is the root, the algorithm should be able to terminate in that for loop.

**Complexity:** O(3n) time and O(n) space

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

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """

        def path_to_x(root, path, x, go):
            if root is not None and go[0]:
                path.append(root.val)
                if root.val == x:
                    go[0] = False
                path_to_x(root.left, path, x, go)
                path_to_x(root.right, path, x, go)
                if go[0]:
                    path.pop()

        path_p = []
        go = [True]
        path_to_x(root, path_p, p, go)

        path_q = []
        go[0] = True
        path_to_x(root, path_q, q, go)

        strt = min(len(path_p), len(path_q)) - 1
        for i in range(strt, -1, -1):
            if path_p[i] == path_q[i]:
                return path_p[i]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/236-lowest-common-ancestor-of-a-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.