An outage detection framework for power distribution networks is proposed. The framework combines the use of optimally deployed real-time power flow sensors and that of load estimates via Advanced Metering Infrastructure (AMI) or load forecasting mechanisms. The distribution network is modeled as a tree network. It is shown that the outage detection problem over the entire network can be decoupled into detection within subtrees, where within each subtree only the sensors at its root and on its boundary are used. Outage detection is then formulated as a hypothesis testing problem, for which a maximum a-posteriori probability (MAP) detector is applied. Employing the maximum misdetection probability Pmax e as the detection performance metric, the problem of finding a set of a minimum number of sensors that keeps P max e below any given probability target is formulated as a combinatorial optimization. Efficient algorithms are proposed that find the globally optimal solutions for this problem, first for line networks, and then for tree networks. Using these algorithms, optimal three-way tradeoffs between the number of sensors, the load estimate accuracy, and the outage detection performance are characterized for line and tree networks using the IEEE 123 node test feeder system.