We study the problem of running full binary tree based algorithms on a hypercube with faulty nodes. The key to this problem is to devise an algorithm for embedding a full binary tree in the faulty hypercube. Supposing that the root of the tree must be mapped to a specified hypercube node, we show how to embed an (n–1)-tree (a full binary tree with 2 ^n–1-1 nodes) into an n-cube (a hypercube with 2ⁿ nodes) having up to n–2 faults. Our embedding has unit dilation and load, and the result is optimal in the sense that the algorithm is time-optimal, the (n–1)-tree is the largest full binary tree that can be embedded in an n-cube, and n–2 faults is the maximum number of faults that can be tolerated when the root is fixed. Furthermore, we also show that any algorithm for this problem cannot be totally recursive in nature.