package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

/**
 * 235. Lowest Common Ancestor of a Binary Search Tree
 *
 * 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).”

 _______6______
 /              \
 ___2__          ___8__
 /      \        /      \
 0      _4       7       9
 /  \
 3   5

 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.

 */
public class _235 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        if ((root.val - p.val) * (root.val - q.val) > 0) {
            if (root.val - p.val > 0) {
                return lowestCommonAncestor(root.left, p, q);
            }
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

@@ -830,16 +830,56 @@
 _235 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -952,32 +952,36 @@
 de q) %7B%0A        
+    
 if (root == null
@@ -1014,32 +1014,36 @@
 ) %7B%0A            
+ 
+   
 return root;%0A   
@@ -1039,34 +1039,42 @@
 n root;%0A        
-%7D%0A
+    %7D%0A    
         if ((roo
@@ -1120,32 +1120,36 @@
 ) %7B%0A            
+ 
+   
 if (root.val - p
@@ -1152,32 +1152,36 @@
  - p.val %3E 0) %7B%0A
+    
                 
@@ -1218,32 +1218,36 @@
 ot.left, p, q);%0A
+    
             %7D%0A  
@@ -1248,32 +1248,36 @@
   %7D%0A            
+    
 return lowestCom
@@ -1307,34 +1307,42 @@
  p, q);%0A        
-%7D%0A
+    %7D%0A    
         return r
@@ -1342,20 +1342,30 @@
 eturn root;%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 235