Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

This means consider 2 nodes A and B, lowest descendant is the last depth node common bw them This means 1. It should be common 2. It should be last / depth last node

Now since its a binary search tree, for the given two nodes (given in question) a. if the both of them are > than the given root node then search is on the right subtree b. if both of them are < than the given root search is on the left subtree c. else just the case that thats the common ancestor

   private Node lowestCommonAncestor(Node tree, Node target1, Node target2) {

        Node parent = tree;
        int node1 = target1.val;
        int node2 = target2.val;

        if(node1 > parent.val && node2 > parent.val) {
            lowestCommonAncestor(tree.right, target1, target2);
        } else if(node1 < parent.val && node2 < parent.val) {
            lowestCommonAncestor(tree.left, target1, target2);
        } else {
            return parent;
        }
     return null;
}

    private Node lowestCommonAncestorIterativeApproach(Node tree, Node target1, Node target2) {

        Node node = tree;
        int node1 = target1.val;
        int node2 = target2.val;

       while (node != null) {
        if(node1 > node.val && node2 > node.val) {
            node = node.right;
        } else if(node1 < node.val && node2 < node.val) {
            node = node.left;
        } else {
            return node;
        }
    }
     return null;
    }