O(n) time non-recursive procedure to traverse a binary tree

Question

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.

You can do it with `O(logn)` extra memory using a stack. No extra memory sounds hard. — Thomas Ahle, Jun 14 '12 at 17:21
I'm not going to use a Stack since it is not O(1) space. It wouldn't make sense either since the previous exercise in the book asks you to write a non-recursive traversal procedure using a stack. — Adam Arold, Jun 14 '12 at 17:22
Is the tree a search tree / ordered? We need a way to remember what we have already printed. — Thomas Ahle, Jun 14 '12 at 17:32
@ThomasAhle you are assuming the tree is balanced, otherwise is `O(n)` extra memory. — Gastón Bengolea, Jun 03 '14 at 22:04

Thomas Ahle · Accepted Answer · 2012-06-15T00:19:50.513

9

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.

edited Jun 15 '12 at 00:19

answered Jun 14 '12 at 17:38

Thomas Ahle

30,774
21
92
114

If I don't start with the root the algorithm must work so you have to store the parent node of the entry node and if you arrive at that node the traversal is over. – Adam Arold Jun 15 '12 at 08:11
This algorithm is flawed. In the case that a node doesn't have a right node then now will be null and the traversal terminates. – Adam Arold Jun 15 '12 at 08:47
Yes, for simplicity it assumes that there are always two children, but I should be easy to extend it with more cases like "if only child is left && old == now.left: go up". – Thomas Ahle Jun 15 '12 at 10:01

romainsalles · Answer 2 · 2014-12-25T11:37:45.667

There is the complete code (in Ruby).

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

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

I hope it helps...

score 0 · Answer 3 · answered Jan 02 '17 at 16:56

You will have to do an in-order walk of the tree. In the same book, there is a hint in the first set of exercises on the chapter dealing with Binary Search Trees. To quote:

There is an easy solution that uses a stack as an auxiliary data structure and a more complicated but elegant solution that uses no stack but assumes that two pointers can be tested for equality.

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

O(n) time non-recursive procedure to traverse a binary tree

3 Answers3