Backbone nodes are effective for routing in wireless networks because they reduce the energy consumption in sensor nodes. Packet delivery only occurs through the backbone nodes, which depletes the energy in the backbone drastically. Several backbone construction algorithms, including energy-aware virtual backbone tree, virtual backbone tree algorithm for minimal energy consumption and multihop cluster-based stable backbone tree, fail to form a complete backbone when converting important nodes, such as a cut vertex tree node to a non-backbone node. Thus we propose a fault-tolerant virtual backbone tree (FTVBT) algorithm that addresses all of these conflicts and we give theoretical derivations of the bounds for the probability that a sensor node can connect with the backbone. Furthermore, randomized FTVBT improves FTVBT by redistributing non-tree nodes randomly among all the eligible tree nodes based on their fitness values, thereby decreasing the rapid depletion of energy in a particular node and increasing the network lifetime. We performed simulations in NS2 and analyzed the experimental results. © 2015 Elsevier Ltd.