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