4 ms·
Constant-space iteration over the elements of a balanced binary tree requires parent pointers and therefore requires circular references.
by nhaehnle 11y ago
Constant-space iteration over the elements of a balanced binary tree requires parent pointers and therefore requires circular references.
- cwzwarich 11y agoThat 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.