# LeetCode: 235. Lowest Common Ancestor of a Binary Search Tree

The problem is here: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ . Using recursive function solve this fast, because of the nature of BST. For each node in BST, every node on left is smaller than root and every node on right. Therefore, the ancestor of two nodes in BST must be a root of sub-tree of root. The following is my solution:

```# 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 or q.val == root.val:
return root

if p.val < root.val:
if q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
else:
return root
else:
if q.val < root.val:
return root
else:
return self.lowestCommonAncestor(root.right, p, q)
```

Recursive function is more elegant than other forms, but if the depth of BST is large, the recursive stack may overflow. Generally, the size of a balanced BST grows exponentially while the depth grows linearly, we won't worry the problem of stack overflow. If it is not balanced, then we could traverse the tree to do this. The following is my solution, no recursion:

```# 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
"""
cur = root
while cur is not None:
if p.val == cur.val or q.val == cur.val:
break
if p.val < cur.val:
if q.val < cur.val:
cur = cur.left
continue
else:
break
else:
if q.val < cur.val:
break
else:
cur = cur.right
continue
return cur
```