We introduce a new set of probabilistic analysis tools based on the analysis of And-Or trees with random inputs. These tools provide an unifying, intuitive, and powerful framework for carrying out the analysis of several previously studied random processes, including random loss-resilient codes, random k-SAT formulae using the pure literal rule, and the greedy algorithm for matchings in random graphs. In addition, these tools allow generalization of these problems not previously analyzed in a straightforward manner. We illustrate our methodology on the three problems listed above.