Look at Morris in-order tree traversal which uses constant space and runs in O(n) (up to 3 times longer than your normal recursive traversal - but you save hugely on space). If the nodes are modifiable, than you could save the calculated result of the sub-tree as you backtrack to its root (by writing directly to the Node).