How can recursion tree split a problem into smaller pieces that do not add up?
Here is a very simple example: binary search.
We are looking for an element $x$ inside a sorted array $A$. We compare $x$ to the element at the middle $m$ of $A$. If $m = x$, we're done. If $m &gt; x$, we recurse on the left half, and if $m &gt; x$, we recurse on the right half. The recurrence for the worst-case running time is
$$ T(n) = T(n/2) + O(1), $$
whose solution is $T(n) = O(\log n)$.