We propose a simple, exactly solvable, model of interface growth in a random medium that is a variant of the zero-temperature random-field Ising model on the Cayley tree. This model is shown to have a phase diagram (critical depinning field versus disorder strength) qualitatively similar to that obtained numerically on the cubic lattice. We then introduce a specifically tailored random graph that allows an exact asymptotic analysis of the height and width of the interface. We characterize the change of morphology of the interface as a function of the disorder strength, a change that is found to take place at a multicritical point along the depinning-transition line.