• 38.4%

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

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

According to the definition of LCA on Wikipedia: “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).”

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

https://discuss.leetcode.com/topic/18614/easy-c-recursive-and-iterative-solutions

Easy C++ Recursive and Iterative Solutions

Well, remember to take advantage of the property of binary search trees, which is, node -> left -> val < node -> val < node -> right -> val. Moreover, both p and q will be the descendants of the root of the subtree that contains both of them. And the root with the largest depth is just the lowest common ancestor. This idea can be turned into the following simple recursive code.

Of course, we can also solve it iteratively.

3 lines with O(1) space, 1-Liners, Alternatives

Just walk down from the whole tree’s root as long as both p and q are in the same subtree (meaning their values are both smaller or both larger than root’s). This walks straight from the root to the LCA, not looking at the rest of the tree, so it’s pretty much as fast as it gets. A few ways to do it:

Iterative, O(1) space

Python

Java

(in case of overflow, I’d do (root.val - (long)p.val) * (root.val - (long)q.val))

Different Python

“Long” Python, maybe easiest to understand

Recursive

Python

Python One-Liner

Java One-Liner

“Long” Python, maybe easiest to understand

https://discuss.leetcode.com/topic/22095/c-solution-40ms

C++ solution . 40ms

https://discuss.leetcode.com/topic/18438/python-iterative-solution

Python Iterative Solution

https://discuss.leetcode.com/topic/19536/my-python-recursive-solution

My Python recursive solution