Space Requirements for Tree Traversal

Re:Space Requirements for Tree Traversal by orange_county on Sunday October 09, 2016 @12:48PM (#12671983)

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.

[ Parent | on HN ]

Re:Space Requirements for Tree Traversal by fpoling on Sunday October 09, 2016 @04:03PM (#12673128)

One does not need to flatten tree if tree modifications are allowed. Just use Deutsch-Schorr-Waite algorithm.

[ Parent | on HN ]

Re:Space Requirements for Tree Traversal by catnaroek on Sunday October 09, 2016 @01:18PM (#12672141)

Are you assuming that nodes have parent pointers?

[ Parent | on HN ]

Re:Space Requirements for Tree Traversal by orange_county on Sunday October 09, 2016 @01:32PM (#12672221)

You 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

[ Parent | on HN ]

Re:Space Requirements for Tree Traversal by catnaroek on Sunday October 09, 2016 @01:54PM (#12672349)

Thanks!

[ Parent | on HN ]