Es el descubridor de numerosos importantes algoritmos de grafos, incluyendo el Algoritmo de Tarjan del mínimo número de ancestros (Tarjan's off-line least common ancestors algorithm), o los splay trees, junto con Daniel Sleator.
Tarjan recibió el Premio Turing de la ACM junto con John Hopcroft en 1986:
Tarjan fue también elegido miembro de la ACM en 1994:
En la Universidad de Stanford, recibió su máster en informática en 1971, doctorándose en 1972.
En Stanford, su tesis doctoral fue supervisada por Robert Floyd y Donald Knuth, ambos científicos de renombre.