If nodes have pointers to their parent, constant space tree traversal is easy enough.