Delete a consecutive range of leaves from a binary tree
Yes.  This can be done in $O(d)$ time.  As a nice consequence, if we have a balanced binary tree, then $d = O(\lg n)$, so range-deletion can be done in $O(\lg n)$ time, regardless of how large the range is.

This is hard to explain without a picture, but the key insight is this: it suffices to delete a set $S$ of nodes, where $S$ can be chosen so that $|S| \le 2d$.  (This will of course delete all of the descendants of every node in $S$.)  Since $|S| = O(d)$, the running time to delete the nodes in $S$ will be $O(d)$.  In other words, the interval $[i,j]$ can be expressed as a union of $O(d)$ subtrees.  Roughly speaking, the set $S$ will be chosen by taking a subset of the siblings of the nodes on the path from $i$ or $j$ to the root.

In particular, we will define

$$S = \{n : L(n) \subseteq [i,j] \text{ and } L(\text{parent}(n)) \not\subseteq [i,j]\},$$

where $L(n)$ is the set of leaves that are descendants of $n$.  I will show first that deleting $S$ has the desired effect, and second that that $|S| \le 2d$, from which it will follow that the range-deletion can be done in $O(\lg d)$ time.

Lemma 1. Deleting $S$ will have the effect of deleting leaves $i,i+1,\dots,j-1,j$ but not any of the other leaves.

Proof. Consider any leaf $\ell$ with $i \le \ell \le j$.  Then $\ell$ is a descendant of some $n \in S$: if $\ell \notin S$, then some ancestor of $S$ must be in $S$ (imaging walking up from $\ell$ along the path towards the root; consider the last ancestor $n$ of $S$ such that $L(n) \subseteq [i,j]$; since $L(\ell) =\{\ell\} \subseteq [i,j]$, such an ancestor must exist).  Conversely, a leaf $\ell$ is deleted only if it is a descendant of some $n \in S$; but by construction, $L(n) \subseteq [i,j]$ and $\ell \in L(n)$, so it follows that if leaf $\ell$ is deleted, $\ell \in [i,j]$.

Now let's show that $|S| \le 2d$.  Let $P(\ell)$ denote the set of nodes along the path from $\ell$ to the root.  Let $Q(\ell)$ denote the set of siblings of the nodes in $P(\ell)$ ($\ell$'s sibling, $\ell$'s parent's sibling, $\ell$'s parent's parent's sibling, and so on).  Then I claim:

Lemma 2. $|Q(\ell)| \le d$ for all $\ell$.

Proof. Since the tree has height $d$, $|P(\ell)| \le d$.  Now $|Q(\ell)| \le |P(\ell)| \le d$.

Lemma 3. $S \subseteq Q(i) \cup Q(j)$.

Proof. Suppose $n \in S$, so that $L(n) \subseteq [i,j]$ but $L(\text{parent}(n)) \not\subseteq [i,j]$.  Let $m$ be $n$'s sibling.  Note that $L(\text{parent}(n)) = L(n) \cup L(m)$.  It follows that we must have $L(m) \not\subseteq [i,j]$ (otherwise $L(\text{parent}(n)) \subseteq [i,j]$ and $n$ wouldn't be in $S$).  Also $L(n) \cap L(m) = \emptyset$ and $L(n)$ and $L(m)$ are adjacent intervals ($L(n) \cup L(m)$ is itself an interval; there is no gap in between $L(n)$ and $L(m)$).  It follows that either $i \in L(m)$ or $j \in L(m)$, i.e., $m$ must be an ancestor of either $i$ or $j$, i.e., either $m \in Q(i)$ or $m \in Q(j)$.

Lemma 4. $|S| \le 2d$.

Proof. Follows from Lemma 2, Lemma 3, and the union bound.



Caveat: I haven't checked whether rebalancing can also be done in $O(d)$ time.  For instance, for a balanced binary tree like an AVL tree or a red-black tree, we have $d=O(\lg n)$, and it would be nice if we could delete the entire range in $O(\lg n)$ time.  However, it's not clear whether this is possible.  While we can indeed delete the nodes in $S$ in $O(\lg n)$ time, I haven't checked whether it's possible to do all necessary subsequent rebalancing operations in $O(\lg n)$ time.  Rebalancing is certainly doable in $O((\lg n)^2)$ time, but I don't know whether it can be done in $O(\lg n)$ time.