A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction--bounded away from $0$--of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman (STOC 1993) and serve as a key ingredient in almost all deterministic interactive coding schemes. The number of colors effects the coding scheme's rate.

It is shown that $4$ is precisely the least number of colors for which tree codes exist. Thus, tree-code-based coding schemes cannot achieve rate larger than $1/2$. To overcome this barrier, a relaxed notion called palette-alternating tree codes is introduced, in which the number of colors can depend on the layer. We prove the existence of such constructs in which most layers use $2$ colors--the bare minimum. The distance-rate tradeoff we obtain matches the Gilbert-Varshamov bound.

Based on palette-alternating tree codes, we devise a deterministic interactive coding scheme against adversarial errors that approaches capacity. To analyze our protocol, we prove a structural result on the location of failed communication-rounds induced by the error pattern enforced by the adversary. Our coding scheme is efficient given an explicit palette-alternating tree codes and serves as an alternative to the scheme obtained by Gelles et al. (SODA 2016)