3 ms·
If you want O(1) space complexity and you do not care about modifying the tree, you can do tree rotations essentially flattening out the tree into a singly link
by orange_county 10y ago
If you want O(1) space complexity and you do not care about modifying the tree, you can do tree rotations essentially flattening out the tree into a singly linked list.
- catnaroek 10y agoAre you assuming that nodes have parent pointers?
- orange_county 10y agoYou don't need parent pointers. For converting binary tree into a linked list in O(n) time and O(1) space. You have two pointers, the root and the tail (right child node). If root has a left subtree, set tail->right = left subtree. Update tail again so it is the last right child node. root = root->right Repeat until root is NULL
- catnaroek 10y agoThanks!
- fpoling 10y agoOne does not need to flatten tree if tree modifications are allowed. Just use Deutsch-Schorr-Waite algorithm.