Turn conditional recursion algorithm to an iterative one

Question

Recently I wrote a recursion-based algorithm to print a binary tree horizontally. Generally I don't have any problems converting recursion-based algorithms to iteration-based ones but I just can't figure out how to do this.

say we a vector

std::vector<int> tree = {10,9,8,7,6,5,4};

which represents the following tree:

     10
    / \
   9   8
  /\   /\
 7 6   5 4

my algorithm works by taking the following routes:

index ->  left -> left      Or in our case 10 -> 9 -> 7
               -> right                            -> 6
      -> right -> left                        -> 8 -> 5
               -> right                            -> 4

etc and expanding depending on the size of the tree. What I can't wrap my mind around is how I can translate the code to while loops when I use recursion conditionally. I am not that good at explaining so here is the code.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unistd.h>

/* The Padding function handles the spacing and the vertical lines whenever we print a  *
 * right child. This depends on the previous parent-child hierarchy of the child        *
 * Printer handles the work of printing the elements and uses a depth-first-search      *
 * algorithm as it's core. Left children are printed horizontally while the right ones  *   
 * are printed vertically. Print_tree is a wrapper. It also finds the max-length value  *
 * which will be used for formatting so that the formatting won't get messed up because *
 * of the different number of digits.                                                   */           

std::string do_padding (unsigned index, unsigned mlength){
  std::string padding;
  while(int((index-1)/2) != 0){
    padding = (int((index-1)/2) % 2 == 0) ?
    std::string(mlength+4,' ') + " "  + padding :
    std::string(mlength+3,' ') + "| " + padding ;
    index = int((index-1)/2);
  }
  return padding;
}

template <class T>
void printer (std::vector<T> const & tree, unsigned index, unsigned mlength){
  auto last = tree.size() - 1 ;
  auto  left = 2 * index + 1 ;
  auto  right = 2 * index + 2 ;
  std::cout << " " << tree[index] << " " ;
  if (left <= last){
    auto llength = std::to_string(tree[left]).size();
    std::cout << "---" << std::string(mlength - llength,'-');
    printer(tree,left,mlength);
    if (right <= last) {
      auto rlength = std::to_string(tree[right]).size();
      std::cout << std::endl<< do_padding(right,mlength) << std::string(mlength+ 3,' ') << "| " ;
      std::cout << std::endl << do_padding(right,mlength) << std::string(mlength+ 3,' ') << "└─" <<
      std::string(mlength - rlength,'-');
      printer(tree,right,mlength);
    }
  }
}

template <class T>
void print_tree (std::vector<T> & tree){
  unsigned mlength = 0;
  for (T & element : tree){
    auto length = std::to_string(element).size();
    if (length > mlength) {
      mlength = length;
    }
  }
  std::cout <<  std::fixed << std::string(mlength- std::to_string(tree[0]).size(),' ') ;
  printer(tree,0,mlength);
}

int main() {
  std::vector<int> test;
  for (auto i =0; i != 200; ++i) {
    test.push_back(rand() % 12200);
  }
  std::make_heap(test.begin(),test.end());
  std::cout << std::endl << "Press ENTER to show heap tree.." << std::endl;
  std::cin.ignore();
  print_tree(test);
  std::cout << std::endl;
}

It's probably not worth rewriting this but I would like to know how to handle such a recursion in case I have to do something similar in the future.

Answer 1

I remember, you posted the Print heap array in tree format question. So, to me (without having read the code), your core algorithm for tree traversal is a DFS.

What you can do to make this recursive algorithm iterative is to use a stack. The stack basically holds all visited nodes and enables to walk back the path it took. An example is given at Iterative DFS vs Recursive DFS and different elements order.

Answer 2

For most algorithms that walk through a tree, you will need an additional data structure if you want to formulate them in a non-recursive way. For depth first traversal (as in your case), you'll typically use a stack (for breadth first traversal, a queue is used...)

In pseudo-code, printing the tree would look like

function print_tree(tree_vector)
  s = new stack<int>()
  s.push(0)
  while (!s.empty())
    index = s.pop()
    print (tree_vector[index])
    left = 2*index + 1
    right = 2*index + 2
    if (right < tree_vector.size())
      s.push(right)
    if (left < tree_vector.size())
      s.push(left)
  end while
end function

Note that this stack implicitely represents the call stack internally used by the compiler when making the recursive calls.