non recursive binary tree traversal in O(n) time and O(1) space - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

non recursive binary tree traversal in O(n) time and O(1) space

non recursive binary tree traversal in O(n) time and O(1) space# JobHunting - 待字闺中

r*e2011-02-12 08:02

1 楼

Question:
Write an O(n)-time nonrecursive procedure that, given an n-node binary tree,
prints out the key of each node. Use no more than constant extra space
outside of the tree itself and do not modify the tree, even temporarily,
during the procedure. Assume each node has a left pointer to its left child
, a right pointer to its right child, and no parent pointer.
Is this possible? Any ideas? Thanks.

v*72011-02-12 08:02

2 楼

tree,
child
I am wondering whether such solution exists. Traversal of a tree without
recursion
can be done by either Queue-based or Stack-based. But if the space required
is no
more than constant, it means that the space allocated to Queue or Stack is
constant.
But I have no idea on how to deal with it by using Q/S with constant space
forever.

【在 r******e 的大作中提到】

: Question:
: Write an O(n)-time nonrecursive procedure that, given an n-node binary tree,
: prints out the key of each node. Use no more than constant extra space
: outside of the tree itself and do not modify the tree, even temporarily,
: during the procedure. Assume each node has a left pointer to its left child
: , a right pointer to its right child, and no parent pointer.
: Is this possible? Any ideas? Thanks.

l*a2011-02-12 08:02

3 楼

Your depth of the tree is non-constant. If there is not parent pointer,
no extra space to store the path from root to current node, how can you go
back once you are in the leaf.

tree,
child

【在 r******e 的大作中提到】

g*s2011-02-12 08:02

4 楼

that's the answer: no way.

go

【在 l*****a 的大作中提到】

: Your depth of the tree is non-constant. If there is not parent pointer,
: no extra space to store the path from root to current node, how can you go
: back once you are in the leaf.
:
: tree,
: child