CODEWITHSUNDEEP
javabinary-treebinary-search-treelowest-common-ancestor
Ibrahim Ahmed
Ibrahim Ahmed

Reputation: 1

Why does my "Lowest common ancestor" function keep returning null when I try to have it search my binary Tree?

public String LCA(String s, String t) throws IllegalArgumentException {
        // Check if s or t are null or not in the tree
        if (s == null || t == null || !stringsToNodes.containsKey(s) || !stringsToNodes.containsKey(t)) {
            throw new IllegalArgumentException("s or t are null or not in the tree");
        }
    
        // Find nodes containing s and t
        Node nodeS = stringsToNodes.get(s);
        Node nodeT = stringsToNodes.get(t);
    
        // Get paths from nodes to the root
        ArrayStack<Node> pathS = getPathToRoot(nodeS);
        ArrayStack<Node> pathT = getPathToRoot(nodeT);
    
        // Find the intersection of paths
        Node lca = findIntersection(pathS, pathT);
    
        // Return the value of the LCA or null if not found
        return lca != null ? lca.s : null;
    }
    
    // method to find the path from a node to the root
    private ArrayStack<Node> getPathToRoot(Node node) {
        ArrayStack<Node> path = new ArrayStack<>();
        while (node != null) {
            path.add(node);
            node = node.parent;
        }
        return path;
    }
    
  // method to find the intersection of two paths
private Node findIntersection(ArrayStack<Node> pathS, ArrayStack<Node> pathT) {
    Node intersect = null;
    
    // Iterate over both paths until one of them is exhausted
    while (!pathS.isEmpty() && !pathT.isEmpty()) {
        Node nodeS = pathS.get(pathS.size() - 1);
        Node nodeT = pathT.get(pathT.size() - 1);
        if (nodeS == nodeT) {
            intersect = nodeS;
        } else {
            break;
        }
        pathS.remove(pathS.size() - 1); // Move to the previous node in pathS
        pathT.remove(pathT.size() - 1); // Move to the previous node in pathT
    }
    
    return intersect;
}

This is my function

I've tried doing it without the private methods, and I wasn't able to find any other solutions online.

Upvotes: 0

Views: 43

Answers (1)

Etnim
Etnim

Reputation: 77

One potential issue could be with the comparison of nodes using == in the findIntersection method. Instead of comparing nodes directly using ==, that compares there references, you should compare their values.

Replace this part of your findIntersection method:

if (nodeS == nodeT) {
    intersect = nodeS;
}

With:

if (nodeS.equals(nodeT)) {
    intersect = nodeS;
}

Upvotes: 2

Related Questions