Currently, I am working on a program, one of whose steps is to check if a leaf c is in the same subtree as two other leaves a and b, in a binary tree T. My current approach is as follows: first, find the LCA of each pairs of leaves in T, and store it in a dictionary. Then, for each node in the tree, find all of the leaves that are descendants of it, and store it in a dictionary as well. Then when I need to determine if c is in the same subtree as a and b, I find the LCA of a and b, and check if c is a descendant of it.
I will need to run this step for many different pairs a and b, and do it on binary trees that have as many as 600 leaves, so is there a faster algorithm, or perhaps one that uses less memory, that does this same task? Thanks.
One useful observation that might help you here is the following: the smallest subtree containing leaves a and b is the subtree rooted at LCA(a, b). This means that you can test whether c is in the subtree by checking whether c is a descendant of LCA(a, b). One way to do this is the following: compute LCA(LCA(a, b), c). If c is in this subtree, then LCA(LCA(a, b), c) = LCA(a, b). Otherwise, it will be some other node. This gives a nice algorithm:
It might also help to use a fast LCA data structure. You mentioned precomputing the LCA of all pairs of nodes in the tree, but there are faster options. In particular, there are some nice algorithms that with O(n) preprocessing time can return the LCA of two nodes in a tree in time O(1) each. If you know the pairs in advance, check out Tarjan's offline LCA algorithm; if you don't, look up the Fischer-Heun LCA data structure.
Hope this helps!