Menu
I'm reading a book called "Introduction to algorithms". I think many of you know it. I just bumped into a question which seems rather difficult:
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.
I saw that there is another question like this: How to traverse a binary tree in O(n) time without extra memory but the main difference is that I can't modify the tree. I was thinking of using some visited flag but I haven't distilled a right solution yet. It's maybe something obvious I don't see. How would you devise an algirithm which solves this problem? Even some pointers to the answer would be appreciated.
332
Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.
1) Create an empty stack S. 2) Initialize current node as root 3) Push the current node to S and set current = current->left until current is NULL 4) If current is NULL and stack is not empty then a) Pop the top item from stack. b) Print the popped item, set current = popped_item->right c) Go to step 3.
In general, time complexity is O(h) where h is height of BST. Insertion: For inserting element 0, it must be inserted as left child of 1. Therefore, we need to traverse all elements (in order 3, 2, 1) to insert 0 which has worst case complexity of O(n). In general, time complexity is O(h).
There are basically three traversal techniques for a binary tree that are, Preorder traversal. Inorder traversal. Postorder traversal.
If the tree is linked in both directions, you can do this:
assert root.parent is null
now, old = root, null
while now != null:
print now.label
if leaf(now):
now, old = now.parent, now
else:
if old == now.right:
now, old = now.parent, now
if old == now.left:
now, old = now.right, now
if old == now.parent:
now, old = now.left, now
This prints in root, left, right order, but you can get any order you like.
I don't think you can do it if the tree is only linked in one direction. You could have a look at Deforestation.
146
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
