Lowest Common Ancestor (LCA) of binary search tree in java

ghz 10months ago ⋅ 78 views

To find the Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST) in Java, you can follow these steps:

  1. Start from the root node.
  2. Traverse the tree recursively.
  3. If both nodes are on the left side of the current node, go left.
  4. If both nodes are on the right side of the current node, go right.
  5. If one node is on the left side and the other is on the right side of the current node, then the current node is the LCA.

Here's the Java code to implement this algorithm:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class LowestCommonAncestorBST {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        // If both nodes are less than the current node value,
        // then the LCA must be in the left subtree.
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        // If both nodes are greater than the current node value,
        // then the LCA must be in the right subtree.
        else if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        // If one node is on the left side and the other is on the right side of the current node,
        // then the current node is the LCA.
        else {
            return root;
        }
    }

    public static void main(String[] args) {
        // Create a sample BST
        TreeNode root = new TreeNode(20);
        root.left = new TreeNode(10);
        root.right = new TreeNode(30);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(15);
        root.right.left = new TreeNode(25);
        root.right.right = new TreeNode(35);

        LowestCommonAncestorBST lcaFinder = new LowestCommonAncestorBST();
        // Nodes to find LCA for
        TreeNode p = root.left.left; // Node with value 5
        TreeNode q = root.left.right; // Node with value 15

        TreeNode lca = lcaFinder.lowestCommonAncestor(root, p, q);
        System.out.println("Lowest Common Ancestor of " + p.val + " and " + q.val + " is: " + lca.val);
    }
}

In this implementation:

  • The lowestCommonAncestor method takes the root node of the BST, along with two nodes p and q, and returns their lowest common ancestor.
  • The method recursively traverses the tree, following the steps outlined above.
  • In the main method, a sample BST is created, and then the lowest common ancestor of two nodes p and q is found and printed.
#algorithm