Space Requirements for Tree Traversal

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 ]