Lowest Common Ancestor in BST

Lowest common ancestor is basically a common node between both child which is nearest to both child & farthest from root.

In order to find the common node, we will have to traverse tree. But again question will be how to reach to common node ?

Let’s try to first find both node which common node we have to find. In BST since node are stored in ordered way i.e smaller in left & larger in right , we need to visit either left or right based on node values.

While visiting if a node does not satisfy the condition to visit next child means if a node is neither going in left & neither going in right then its our common ancestor node.

let’s try to understand above tree -

We have to find common nodes between 5 and 14. So we start traversing from root -

ITERATIONS -

1. We are on root node which value is 15. We compare with root (5<15 && 14<15) which means 5 and 14 lies in left of root node, so we set our pointer to left of root node which is 10.
2. We compare with 10 - 4<10 but 14 < 10 is false. So here we can’ go in left or right direction. And this means 10 is our common node.

Let’s convert above approach into code —

findLowestCommonAncestor(n1, n2) {
    function find(root) {
        if (root == null) {
            return;
        }
        if (n1 < root.data && n2 < root.data) {
            return find(root.left);
        }
        if (n1 > root.data && n2 > root.data) {
            return find(root.right);
        }
        // this is common node
        return root.data;
    }
    return find(this.root);
}

So we are going either in left direction or in right direction and if we can’t go in any then return the result.

Now let’s write complete code —

class Node {
    constructor(value) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}
class BinarySearchTree {
add(value) {
        let node = new Node(value);
        let current = this.root;
        if (current == null) {
            this.root = node;
        } else {
            while (current != null) {
                if (value < current.data) {
                    if (current.left == null) {
                        current.left = node;
                        current = null;
                    } else {
                        current = current.left;
                    }
                } else {
                    if (current.right == null) {
                        current.right = node;
                        current = null;
                    } else {
                        current = current.right;
                    }
                }
            }
        }
    }
    addMany(...args) {
        args.forEach(item => {
            this.add(item);
        })
    }
    inOrder() {
        // console.log("root", JSON.stringify(this.root));
        function traverse(root) {
            if (root == null) {
                return;
            }
            traverse(root.left);
            console.log(root.data);
            traverse(root.right);
        }
        traverse(this.root);
    }
    findLowestCommonAncestor(n1, n2) {
        function find(root) {
            if (root == null) {
                return;
            }
            if (n1 < root.data && n2 < root.data) {
                return find(root.left);
            }
            if (n1 > root.data && n2 > root.data) {
                return find(root.right);
            }
            return root.data;
        }
        return find(this.root);
    }
}
const tree = new BinarySearchTree();
tree.addMany(20, 8, 22, 4, 12, 10, 14);
console.log(tree.findLowestCommonAncestor(10, 14)); // 12

Hope you are able to understand. Don’t forget to clap and share with your friend.