P2P networks have been proposed as a scalable, inexpensive solution to the problem of distributing multimedia content over the Internet. Since real P2P systems exhibit considerable heterogeneity in hardware, software and network connections, the design of P2P streaming networks must factor in this variation. There are two different sources of heterogeneity in P2P networks. Most existing work in the literature handle heterogeneity among receivers and requirements by the use of different multimedia encodings of the same content. In this paper, we focus on the problems caused by heterogeneity in the network delays connecting receivers to the sender. We assume that there is a single multicast tree and a single video stream. We propose new algorithms for building multicast trees for multimedia streaming in heterogeneous P2P networks. Our algorithms differ in the amount of communication and computational resources they require. We compare the performance (using simulations) of our algorithms with an existing algorithm Zigzag [20, 21]. Our results show that two of our algorithms (algorithm FollowTree-Landmark-II and algorithm FollowTree) significantly outperform Zigzag.