# 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:

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