Lowest Common Ancestor

Problem Statement

Write a Java program that extends a Binary Search Tree (BST) implementation to include a method that finds the lowest common ancestor (LCA) of two nodes given their values. The LCA is the deepest node that is an ancestor of both nodes. The program should reuse the BST node structure and test the LCA method with different pairs of values, including cases where both nodes exist, one or both don’t exist, and edge cases like empty trees or single-node trees. The BST property (left subtree values < node value < right subtree values) should be leveraged for efficiency. You can visualize this as finding the closest common ancestor in a family tree for two individuals, using the ordered structure to navigate efficiently.

Input:

• A BST represented by nodes with integer values.
• Two integer values, value1 and value2, representing the nodes to find the LCA for. Output: The value of the LCA node, or -1 if the LCA cannot be determined (e.g., one or both values don’t exist), and a string representation of the tree for clarity. Constraints:
• The tree has between 0 and 10^5 nodes.
• Node values, value1, and value2 are integers in the range [-10^9, 10^9].
• Duplicate values are not allowed in the BST. Example:
• Input: Tree = [5, left: [3, left: [1], right: [4]], right: [7]], Values = [1, 4]
• Output: LCA = 3, "Preorder: 5 3 1 4 7"
• Explanation: Node 3 is the LCA of nodes 1 and 4 (deepest common ancestor).
• Input: Tree = [5, left: [3, left: [1], right: [4]], right: [7]], Values = [1, 6]
• Output: LCA = -1, "Preorder: 5 3 1 4 7"
• Explanation: Node 6 doesn’t exist, so no LCA.
• Input: Tree = [], Values = [1, 2]
• Output: LCA = -1, "Empty"
• Explanation: Empty tree, no LCA.

Pseudocode

CLASS Node
    SET value to integer
    SET left to Node (null by default)
    SET right to Node (null by default)
ENDCLASS

FUNCTION findLCA(root, value1, value2)
    FUNCTION exists(node, value)
        IF node is null THEN
            RETURN false
        ENDIF
        IF node.value equals value THEN
            RETURN true
        ENDIF
        IF value < node.value THEN
            RETURN exists(node.left, value)
        ELSE
            RETURN exists(node.right, value)
        ENDIF
    ENDFUNCTION
    IF root is null OR NOT exists(root, value1) OR NOT exists(root, value2) THEN
        RETURN -1
    ENDIF
    SET current to root
    WHILE current is not null
        IF value1 < current.value AND value2 < current.value THEN
            SET current to current.left
        ELSE IF value1 > current.value AND value2 > current.value THEN
            SET current to current.right
        ELSE
            RETURN current.value
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

FUNCTION toString(root)
    IF root is null THEN
        RETURN "Empty"
    ENDIF
    CREATE result as new StringBuilder
    FUNCTION preorder(node)
        IF node is null THEN
            RETURN
        ENDIF
        APPEND node.value and " " to result
        CALL preorder(node.left)
        CALL preorder(node.right)
    ENDFUNCTION
    CALL preorder(root)
    RETURN "Preorder: " + result as string trimmed
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (tree, value1, value2) pairs
    FOR each testCase in testCases
        PRINT test case details
        CALL findLCA(testCase.root, testCase.value1, testCase.value2)
        PRINT LCA and tree using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Reuse the Node class with: a. An integer value. b. left and right pointers to child nodes.
2. Define findLCA: a. Check if both value1 and value2 exist in the tree using a helper function exists. b. If the tree is empty or either value doesn’t exist, return -1. c. Iteratively traverse from the root:
   • If both values are less than the current node’s value, move to the left child.
   • If both values are greater than the current node’s value, move to the right child.
   • Otherwise, the current node is the LCA (values split or one matches the node). d. Return the LCA’s value, or -1 if not found.
3. Define toString: a. If root is null, return "Empty". b. Perform preorder traversal, appending values to a string.
4. In main, test with: a. A pair where both nodes exist (LCA in subtree). b. A pair where one node doesn’t exist. c. An empty tree. d. A single-node tree with matching and non-matching pairs.

Java Implementation

public class LowestCommonAncestor {
    // Node class for the binary search tree
    static class Node {
        int value;
        Node left, right;

        Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    // Finds the lowest common ancestor of two values
    public int findLCA(Node root, int value1, int value2) {
        // Helper function to check if a value exists in the BST
        boolean exists(Node node, int value) {
            if (node == null) {
                return false;
            }
            if (node.value == value) {
                return true;
            }
            if (value < node.value) {
                return exists(node.left, value);
            } else {
                return exists(node.right, value);
            }
        }

        // Check if both values exist
        if (root == null || !exists(root, value1) || !exists(root, value2)) {
            return -1;
        }

        // Iterative LCA search
        Node current = root;
        while (current != null) {
            if (value1 < current.value && value2 < current.value) {
                current = current.left;
            } else if (value1 > current.value && value2 > current.value) {
                current = current.right;
            } else {
                return current.value;
            }
        }
        return -1;
    }

    // Converts tree to string (preorder traversal)
    public String toString(Node root) {
        if (root == null) {
            return "Empty";
        }
        StringBuilder result = new StringBuilder();
        preorder(root, result);
        return "Preorder: " + result.toString().trim();
    }

    private void preorder(Node node, StringBuilder result) {
        if (node == null) {
            return;
        }
        result.append(node.value).append(" ");
        preorder(node.left, result);
        preorder(node.right, result);
    }

    // Helper class for test cases
    static class TestCase {
        Node root;
        int value1, value2;

        TestCase(int[] values, int[][] edges, int value1, int value2) {
            this.value1 = value1;
            this.value2 = value2;
            if (values.length == 0) {
                root = null;
                return;
            }
            Node[] nodes = new Node[values.length];
            for (int i = 0; i < values.length; i++) {
                nodes[i] = new Node(values[i]);
            }
            for (int[] edge : edges) {
                int parent = edge[0], child = edge[1];
                if (edge[2] == 0) {
                    nodes[parent].left = nodes[child];
                } else {
                    nodes[parent].right = nodes[child];
                }
            }
            root = nodes[0];
        }
    }

    // Main method to test LCA
    public static void main(String[] args) {
        LowestCommonAncestor lcaFinder = new LowestCommonAncestor();

        // Test cases
        TestCase[] testCases = {
            // Both nodes exist: [5, left: [3, left: 1, right: 4], right: 7], values [1, 4]
            new TestCase(
                new int[]{5, 3, 1, 4, 7},
                new int[][]{{0, 1, 0}, {0, 4, 1}, {1, 2, 0}, {1, 3, 1}},
                1, 4
            ),
            // One node doesn’t exist: [5, left: [3, left: 1, right: 4], right: 7], values [1, 6]
            new TestCase(
                new int[]{5, 3, 1, 4, 7},
                new int[][]{{0, 1, 0}, {0, 4, 1}, {1, 2, 0}, {1, 3, 1}},
                1, 6
            ),
            // Empty tree: [], values [1, 2]
            new TestCase(new int[]{}, new int[][]{}, 1, 2),
            // Single node, matching pair: [10], values [10, 10]
            new TestCase(new int[]{10}, new int[][]{}, 10, 10),
            // Single node, non-matching pair: [10], values [10, 20]
            new TestCase(new int[]{10}, new int[][]{}, 10, 20)
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Tree: " + lcaFinder.toString(testCases[i].root));
            System.out.println("Values: [" + testCases[i].value1 + ", " + testCases[i].value2 + "]");
            int lca = lcaFinder.findLCA(testCases[i].root, testCases[i].value1, testCases[i].value2);
            System.out.println("LCA: " + lca + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Tree: Preorder: 5 3 1 4 7
Values: [1, 4]
LCA: 3

Test case 2:
Tree: Preorder: 5 3 1 4 7
Values: [1, 6]
LCA: -1

Test case 3:
Tree: Empty
Values: [1, 2]
LCA: -1

Test case 4:
Tree: Preorder: 10
Values: [10, 10]
LCA: 10

Test case 5:
Tree: Preorder: 10
Values: [10, 20]
LCA: -1

Explanation:

• Test case 1: LCA of 1 and 4 is 3 (deepest common ancestor).
• Test case 2: Node 6 doesn’t exist, so LCA is -1.
• Test case 3: Empty tree, LCA is -1.
• Test case 4: Both values are 10, LCA is 10 (same node).
• Test case 5: Node 20 doesn’t exist, LCA is -1.

How It Works

• Node: Stores an integer value and pointers to left and right children.
• findLCA:
  • Uses exists helper to verify both value1 and value2 are in the tree.
  • If tree is empty or either value is missing, returns -1.
  • Iteratively traverses: if both values are less than current node, go left; if both greater, go right; otherwise, current node is LCA.
• toString: Performs preorder traversal, returns space-separated values or "Empty".
• Example Trace (Test case 1):
  • Verify 1 and 4 exist: true.
  • Root=5: 1 < 5, 4 < 5, go left.
  • Node=3: 1 ≤ 3, 4 > 3, return 3 (split point).
• Main Method: Tests existing nodes, non-existing node, empty tree, single node with matching and non-matching pairs.

Complexity Analysis Table

Note:

• n is the number of nodes in the tree.
• h is the height of the tree (O(n) for skewed, O(log n) for balanced).
• Time complexity: O(h) for findLCA (traverse to LCA and check existence); O(n) for toString (visit all nodes).
• Space complexity: O(h) for recursion stack in exists and toString.
• Worst case: O(n) time and O(n) space for skewed trees.

✅ Tip: Leverage the BST property to find the LCA efficiently by moving left or right based on both values’ relation to the current node. Verify node existence to handle invalid inputs.

⚠ Warning: Ensure both values exist in the tree before computing the LCA to avoid incorrect results. Handle edge cases like empty trees or identical values correctly.