Lowest Common Ancestor Of A Binary Search Tree failing at a long input case

Question

Problem

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).”

Link to Problem Statement

Logic

To have two queues of the path (traversing based on binary search tree logic) and then traverse both queues, and once you find a discrepancy return previous node. I am aware that you can somehow do it without queues using BST logic, and I will optimize it eventually. But I am just wondering why this is not working.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        queueForp = collections.deque()
        queueForq = collections.deque()
        phead = root
        qhead = root
        while phead != None:
            queueForp.append(phead)
            if phead == p:
                phead = None
            else:
                if phead.val < p.val:
                    phead = phead.right
                else:
                    phead = phead.left

        while qhead!= None:
            queueForq.append(qhead)
            if qhead == q:
                qhead = None
            else:
                if qhead.val < q.val:
                    qhead = qhead.right
                if qhead.val > q.val:
                    qhead = qhead.left
        print(queueForp)
        print(queueForq)
        prev = None
        while len(queueForp)!= 0 and len(queueForq) != 0:
            currp = queueForp.popleft()
            currq = queueForq.popleft()
            if currp.val == currq.val:
                prev = currp
            else:
                return prev
        
        
        return prev

Issue

It fails on a really large input about 10k

https://imgur.com/a/tvmp9wM

p = 5893
q = 3379

Output: 41 Expected: 5734 Alternatively, you could try putting this code in leetcode and get the test case. What am I doing wrong?

Answer 1

// Recursive Java program to print lca of two nodes

// A binary tree node
class Node {
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    /* Function to find LCA of n1 and n2. The function
    assumes that both n1 and n2 are present in BST */
    Node lca(Node node, int n1, int n2)
    {
        if (node == null)
            return null;

        // If both n1 and n2 are smaller than root, then LCA
        // lies in left
        if (node.data > n1 && node.data > n2)
            return lca(node.left, n1, n2);

        // If both n1 and n2 are greater than root, then LCA
        // lies in right
        if (node.data < n1 && node.data < n2)
            return lca(node.right, n1, n2);

        return node;
    }

    /* Driver code */
    public static void main(String args[])
    {
        // Let us construct the BST shown in the above
        // figure
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(20);
        tree.root.left = new Node(8);
        tree.root.right = new Node(22);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(12);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(14);

        // Function calls
        int n1 = 10, n2 = 14;
        Node t = tree.lca(tree.root, n1, n2);
        System.out.println("LCA of " + n1 + " and " + n2
                        + " is " + t.data);

        n1 = 14;
        n2 = 8;
        t = tree.lca(tree.root, n1, n2);
        System.out.println("LCA of " + n1 + " and " + n2
                        + " is " + t.data);

        n1 = 10;
        n2 = 22;
        t = tree.lca(tree.root, n1, n2);
    }
}