# Tag Info

Let us prove by induction on depth that for every node $v$, there exist $a_v,b_v$ (possibly $\pm \infty$) such that the input $x$ reaches $v$ iff $a_v < x < b_v$. This is true for the root since we can take $a_r = -\infty$ and $b_r = +\infty$. Now suppose that it is true for some node $v$, and let $v_<,v_>$ be its two children. Suppose that node \$...