# python's most recent public ancestor is LeetCode No.236 No.235 in the binary tree and in the binary search tree

Train of thought: it is very easy to write this question through recursive thinking. Imagine a certain state, p,q on both sides of root respectively. What does that mean? Does it mean that p and q are separated at root? That's where we found it. Let's imagine that if p and q are on the same side, then we'll look for them. For example, if p and q are on the left subtree, then we'll pass down the left subtree of the root node, which is the same as the right subtree.

```# 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
"""
if root is None or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p , q)
right = self.lowestCommonAncestor(root.right, p, q)
# if left is None:
#     return right
# elif right is None:
#     return left
# else:
#     return root
#In the following line, expand on (1)
return right if left is None else left if right is None else root
```

The same way of thinking can also write 235 questions, but not a binary tree, is a binary search tree. According to the properties of binary search tree.

```# 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
"""
#  if p.val< root.val >q.val:
#     return self.lowestCommonAncestor(root.left, p, q)
# if p.val> root.val <q.val:
#     return self.lowestCommonAncestor(root.right, p, q)
#return root
#One line of writing, expand as above
return self.lowestCommonAncestor(root.left, p, q) if p.val< root.val >q.val else  self.lowestCommonAncestor(root.right, p, q) if p.val> root.val <q.val else root

```
```#Non-recursive Writing
# 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
"""
while root:
if p.val <root.val >q.val:
root = root.left
elif p.val> root.val < p.val:
root = root.right
else:
return root

```

Added by Aethaellyn on Tue, 08 Oct 2019 08:51:03 +0300