Geek Answers Handbook

O (n) non-recursive procedure for moving a binary tree

I am reading a book called Introduction to Algorithms . I think many of you know this. I just came across a question that seems rather complicated:

Write a non-recursive O (n) -time procedure that, given the binary tree of n-node, derives a key from each node. Use nothing more than constant additional space outside the tree itself and do not modify the tree, even temporarily, during the procedure.

I saw that there is another such question: How to traverse a binary tree in O (n) time without additional memory , but the main difference is that I can Do not modify the tree. I was thinking about using some kind of visited flag, but I haven't remade the correct solution yet. It may be something obvious that I do not see. How would you develop algerism that solves this problem? Even some answer pointers would be appreciated.

+4
source share
3 answers

If the tree is connected 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

It prints in root, left, right order, but you can get any order you like.

I do not think you can do this if the tree is connected in only one direction. You can watch Deforestation .

+6
source

There is full code (in Ruby).

As an example, I reproduced the same "n-node binary tree" as in the book "Introduction to Algorithms" .

 class Node attr_accessor :key, :parent, :left, :right def initialize(key, parent) @key = key @parent = parent end end class Tree def initialize(root) @root = root end def print_with_constant_space current, old = @root, nil while current do # Going UP if old && old.parent == current # Go right if exists # otherwise continue up next_node = (current.right || current.parent) current, old = next_node, current # Going DOWN else puts current.key # Go left if exists # otherwise go right if exists # otherwise go up next_node = (current.left || current.right || current.parent) current, old = next_node, current end end end end root = Node.new(0, nil) root.left = (node_1 = Node.new(1, root)) node_1.left = (node_2 = Node.new(2, node_1)) node_2.right = (node_3 = Node.new(3, node_1)) node_3.left = (node_4 = Node.new(4, node_3)) node_1.right = (node_5 = Node.new(5, root)) node_5.left = (node_6 = Node.new(6, node_5)) node_6.right = (node_7 = Node.new(7, node_5)) node_7.right = (node_8 = Node.new(8, node_5)) node_8.left = (node_9 = Node.new(9, node_8)) node_9.right = (node_10 = Node.new(10, node_8)) node_8.right = (node_11 = Node.new(11, node_5)) node_5.right = (node_12 = Node.new(12, root)) node_12.left = (node_13 = Node.new(13, node_12)) tree = Tree.new(root) tree.print_with_constant_space

Hope this helps ...

0
source

You will need to do a normal tree walk. In the same book, there is a hint of the first set of exercises in the chapter on binary search trees. Quote:

There is a simple solution that uses the stack as an auxiliary data structure and a more complex but elegant solution that does not use the stack but assumes that two pointers can be checked for equality.

You can find the implementation here: http://tech.technoflirt.com/2011/03/04/non-recursive-tree-traversal-in-on-using-constant-space/

0
source

More articles:


All Articles