A communication tree is a binomial tree embedded in a hypercube, whose communication direction is from its leaves to its root. If a problem to be solved is first divided into independent subproblems, then each subproblem can be solved by one of the hypercube processors, and all the subresults can be merged into the final results through tree communication. This paper uses two random search techniques, the genetic algorithm (GA) and simulated annealing (SA), to construct fault-tolerant communication trees with the minimum data transmission time. Experimental evaluation shows that, with reasonably low search time, the proposed GA and SA approaches are able to find more desirable communication trees (i.e., trees with less data transmission time) than the minimal cost approach can. A distributed approach which applies parallel search to communication subtrees in disjoint subcubes is also provided to reduce the search time of the proposed approaches.