> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-07-2022-237.md).

# 01/07/2022 237

class Solution

This question makes use of the feature of Binary Search Tree. The left node value is less than the root node while the right node value is greater than the root value.  So we compare the node p and q value with the root value. There are only 3 conditions. If both p and q are less than root, we recursively call the function with (root.left, p,q) if both p and q are both greater than the root, we recursively call the function with (root.right, p,q). Otherwise, we just return root if p and q are in different branches. We also can use an iteratvie way to do this question in the same logic. 

recursion T O(N), Space O(N) worst case

iteration way T O(N) SPACE O(1)

// recursive 

{ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

```
    int pVal = p.val;
    int qVal = q.val;
    
    if (pVal < root.val && qVal < root.val){
        return lowestCommonAncestor(root.left, p, q);
    } else if(pVal > root.val && qVal > root.val) {
        return lowestCommonAncestor(root.right, p, q);     
    } else
        return root;
}
```

}

//iterative way

```
    
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  
    int pVal = p.val;
    int qVal = q.val;
    
    while (root != null){
        if (pVal < root.val && qVal < root.val){
            root = root.left;   
        }else if (pVal > root.val && qVal > root.val){
            root = root.right;
        }else{
            return root;
        }
            
    }
    
    return null;
}
```