search algorithms – Finding 2 nodes which sum equals twice their common ancestor in RBT in $Theta(nlg n)$

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:

 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(nlg 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)$