/**
 * 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.
 *
 * Tags: Tree
 *
 * Similar Problems: (M) Lowest Common Ancestor of a Binary Tree
 */
public class LowestCommonAncestorOfBST {

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

    public class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}

@@ -1,8 +1,117 @@
+package com.freetymekiyan.algorithms.level.easy;%0A%0Aimport com.freetymekiyan.algorithms.utils.Utils.TreeNode;%0A%0A
 /**%0A * G
@@ -210,24 +210,28 @@
  the BST.%0A *
+ %3Cp%3E
 %0A * Accordin
@@ -457,20 +457,23 @@
 lf).%E2%80%9D%0A *
+ %7C
 %0A * 
+%7C
         
@@ -489,24 +489,25 @@
 _6______%0A * 
+%7C
           / 
@@ -520,24 +520,25 @@
        %5C%0A * 
+%7C
       ___2__
@@ -553,24 +553,25 @@
   ___8__%0A * 
+%7C
      /      
@@ -587,24 +587,25 @@
 /      %5C%0A * 
+%7C
     0      _
@@ -621,24 +621,25 @@
        9%0A * 
+%7C
           / 
@@ -644,16 +644,17 @@
 /  %5C%0A * 
+%7C
         
@@ -662,16 +662,18 @@
 3   5%0A *
+ %7C
 %0A * For 
@@ -735,24 +735,28 @@
 d 8 is 6.%0A *
+ %3Cp%3E
 %0A * Another 
@@ -856,16 +856,19 @@
  the LCA
+%0A *
  definit
@@ -874,16 +874,74 @@
 tion.%0A *
+ %3Cp%3E%0A * Company Tags: Amazon, Microsoft, Facebook, Twitter
 %0A * Tags
@@ -951,11 +951,8 @@
 ree%0A
- *%0A
  * S
@@ -1054,24 +1054,370 @@
 torOfBST %7B%0A%0A
+    /**%0A     * Iterative.%0A     * In BST, the lca's value can only be %5Bp, q%5D.%0A     * And lca is the first from top to bottom that lies in range.%0A     * If the value is less than both p and q's values, move to right subtree.%0A     * If the value is more than both p and q's values, move to left subtree.%0A     * Otherwise, we found the node.%0A     */%0A
     public T
@@ -1803,45 +1803,209 @@
 ull;
-%0A    %7D%0A%0A    public class TreeNode
+ // Reach null and lca not found.%0A    %7D%0A%0A    /**%0A     * Recursive.%0A     * LCA's value must be between %5Bp, q%5D.%0A     */%0A    public TreeNode lowestCommonAncestorB(TreeNode root, TreeNode p, TreeNode q)
  %7B%0A
-%0A
     
@@ -2013,120 +2013,322 @@
    i
-nt val;%0A        TreeNode left;%0A        TreeNode right;%0A%0A        TreeNode(int x) %7B%0A            val = x;%0A        %7D
+f (root == null) %7B%0A            return null;%0A        %7D%0A        if (root.val %3C p.val && root.val %3C q.val) %7B%0A            return lowestCommonAncestorB(root.right, p, q);%0A        %7D else if (root.val %3E p.val && root.val %3E q.val) %7B%0A            return lowestCommonAncestorB(root.left, p, q);%0A        %7D%0A        return root;
 %0A   

update lowest common ancestor of BST