Is it possible to iterate through a binary tree using iteration instead of recursion?

Question

In school, when we need to iterate through a tree (e.g. binary search tree), we were always taught to iterate through the tree recursively.

Since every recusion can be written as iteration, is it possible to solely use iteration to access the elements of a tree?

I am asking this in context of C++

Answer 1

Concerning the in-order traversal of the binary tree, it is possible to implement the increment and decrement operations by using the Morris traversal in the following way.

Implementation

// (1) increment operation
Node* inc(Node* x)
{
  if(x->right != nullptr){
    x = x->right;
    while(x->left != nullptr)
      x = x->left;
  }
  else{
    while(x == x->parent->right)
      x = x->parent;
    x = x->parent;
  }
  return x;
}

// (2) decrement operation
Node* dec(Node* x)
{
  if(x->left != nullptr){
    x = x->left;
    while(x->right != nullptr)
      x = x->right;
  }
  else{
    while(x == x->parent->left)
      x = x->parent;
    x = x->parent;
  }
  return x;
}

Algorithm

The increment operation is performed in two ways, depending on whether the current node have or do not have a right-child.

In the first case, the successor is the leftmost node of the right subtree of the current node. This means that it is sufficient to move to the right-child node and then proceed along the path of the left-child nodes. In the second case, the current node is already the rightmost element of the left subtree, and therefore there are no greater elements within it. It is necessary to move to the parent node of the subtree, ascending the path of the right-child nodes until the root is reached and then landing on its parent.

Similar reasoning can be done for the decrement operation, but right-child and left-child nodes are inverted.

Answer 2

It may be more common to want to walk a binary tree in sorted order (left to right) as opposed to top to bottom as most common use case for binary trees are around sorted collections. Generally speaking any algorithm that is implemented in recursion can be converted into recursion free algorithm that makes use of stack where stack typically will contain same arguments that are normally passed to function.

Let's start from analysing and understanding what exactly happens in recursive algorithm:

def walk(node):
  # 1. push all left most items on queue, the last item on queue will be the smallest
  if(node.left)
    walk(node.left)

  # 2. print current item - since this is last on stack and we
  # built stack by pushing left most items first, item being
  # printed is guaranteed to always be smallest of those that have not
  # yet been visited
  print(node.key)

  # 3. repeat step 1. and step 2. with node.right
  if(node.right)
    walk(node.right)

let's see what happens if we apply this algorithm on tree

      D
  B       F 
A   C   E   G

                         Stack:
walk(D)                  [D]
  walk(D.left -> B)      [D, B]
    walk(B.left -> A)    [D, B, A]
      print(A)           [D, B, A]
      end of walk A      [D, B]
    print(B)             [D, B]
    walk(B.right -> C)   [D, B, C]
      print(C)           [D, B, C]
      end of walk C      [D, B]
    end of B             [D]
  print(D)               [D]
  walk(D.right -> F)     [D, F]
    ...                  ...

Now we unwrap it from recursion:

1. Start by walking down into lowest node, adding every node on the way to stack

stack = []
next = root.next
while next:
   stack.push(next)
   next = next.next

2. Pop node from stack, print it. This always prints lowest node and we can assume if there was any lower nodes they had already been processed.

while len(stack) > 0:
   node = stack.pop()
   print(node.name)

3. Every time we print a node, we check if node has "right" - if it does, we repeat step 1 by walking into smallest node and adding it on queue

while len(stack) > 0:
   node = stack.pop()
   print(node.name)
   next = node.right
   while(next):
     stack.push(next)
     next = next.left

Stack size will never exceed the tree height thus it can be allocated prior to iterating.

One good reason why we might want to use recursion unrwapping is so that we could wrap this algorithm with iterator pattern:

class TreeIterator:
  __init__(self, root):
     self.stack = []
     next = root
     while(next):
       self.stack.push(next)
       next = root.next

  def next(self):
     if(len(self.stack) == 0)
        return null

     current = self.stack.pop()
     next = current.right
     while(next):
       self.stack.push(next)
       next = next.left

     return current.key


def main():
   tree = {
       key: 'D',
       left: {key: 'B', left: {key: 'A', right: 'C'}},
       right: {key: 'F', left: {key: 'E', right: 'G'}}
   }

   i = TreeIterator(tree)
   while(next = i.next()):
      print(next)

Answer 3

The most common implementation of std::set and std::map is a Red-Black Tree; both can be iterated over with only two iterators (obtained by calls to begin and end); thus, not only is it possible to iterate without recursion, it's even possible to iterate in O(1) space providing the tree is structured correctly.

There are multiple representations for a tree:

• parent to children access: the parent may have one pointer to the first child, a pointer to the first and last children or an array of pointers to each child
• children to parent access: a child may or may not have a pointer to its parent
• sibling access: a child may or may not have a pointer to its predecessor and successor

In general, if:

• a child has a pointer to its parent
• it's possible to access the first child of a parent and know when you reach the last child

then you can implementation iteration in O(1) space; and you may even chose to "visit" the parent right before, in the middle of, or right after its children.

Answer 4

Yes.

For each node you process, store the children into a queue. This goes on for the rest of the nodes in the same level. After processing all the nodes in that level, you then process the queued children. In turn, you store the children's children into the queue. This goes on until you hit the bottom.

For instance the following:

      D
  B       F 
A   C   E   G

// 1
Current: D
Queue: B, F

// 2
Current: B, F
Queue: A, C, E, G

// 3
Current: A, C, E, G
Queue: no more!

Iteration is much more intricate than recursion since you need to implement a queue (if not provided) as well as some additional logic for unbalanced trees. However, iteration is more "memory-friendly" because your queue is just a bunch of pointers to nodes whereas recursion eats up the stack per call.

Answer 5

The answer is yes.

It depends on what kind of traversal you want to do (Preorder, Inorder, Postorder). If you want to replicate the recursive behavior then you need to simulate the stack recursion. It may be useful in a few scenarios but recursion is simpler.

Answer 6

Yes. There exists a method called threading of a tree, which basically joins the nodes in a particular traversal order. So, you can traverse through the whole tree iteratively just like any other traversal recursively.