Finding 2 nodes which sum equals twice their common ancestor in RBT in $\Theta(n\lg n)$

Question

I have a red black tree, $T$, and I need to write an algorithm to find 2 nodes $x$ and $y$ so that $key[x] + key[y] = 2 \cdot key[p(x, y)]$, where $p(x, y)$ is the lowest common ancestor of $x$ and $y$, i.e $x$ is a node on $p(x, y)$'s left subtree and $y$ a node on the right subtree (or the other way around)

My original solution:

FIND-XY(root)
 1. x <- TREE-MIN(root)
 2. y <- TREE-MAX(root)
 3. sum <- x + y
 4. while x != root and y != root and sum != 2 * key[root]
 5.   if sum < 2 * key[root[T]]
 6.    x <- TREE-SUCCESSOR(x)
 7.   else
 8.    y <- TREE-PREDECESSOR(y)
 9.   sum <- x + y
 10. if sum = 2 * key[root]
 11.   return x, y
 12. return null

then for every node in the tree that isn't a leaf I will run FIND-XY with himself as root. FIND-XY runs in $\Theta(n)$ but there are $O(n)$ nodes that aren't leaves so the total run time is $O(n ^ 2)$

I know that there are $O(n)$ nodes that can be $p(x, y)$ so if I can change FIND-XY to run in $O(\lg n)$ then my original algorithm will run in $O(n\lg n)$, but this seems unlikely as finding these $x$, $y$ for the entire tree requires traversing in-order on all $n$ nodes in the tree which is $O(n)$

Answer 1

Your algorithm is correct (it runs in time $O(n\log n)$). What you need is a tighter analysis of the runtime.

Look at the depth of each node in the tree. If two nodes has the same depth, then one can clearly not be the ancestor of the other, and their respective subtrees are also disjoint. Therefore, if you look at all the nodes at a given depth $k$, the sum of the sizes of all subtrees under these nodes can not exceed $n$. Thus, running your algorithm on all of these nodes can also be done in time $O(n)$.

Secondly, as you are working on a red-black tree, the maximum depth of any node is $O(\log n)$. The runtime follows easily.