That isn't strictly true. If you add the qualifier "without mutating the tree" then you are correct. Otherwise, you can avoid parent pointers by reversing poin

That isn't strictly true. If you add the qualifier "without mutating the tree" then you are correct. Otherwise, you can avoid parent pointers by reversing pointers while you traverse, but this requires using a bit per node (which you can generally steal from a pointer in practice) to indicate whether a visited node was the left or right child of its parent. Getting rid of the extra bit is trickier, but it can be done, e.g. Robson traversal that uses the links of leaf nodes to store the stack.