Print ancestors of a given binary tree node without recursion

#include <stdio.h>
#include <stack>

struct TreeNode
{
  TreeNode *left, *right;
  int el;

  explicit TreeNode(int _el) : left(NULL), right(NULL), el(_el) {}
};

typedef TreeNode* Tree;

struct StackNode
{
  TreeNode *node;
  bool visited;

  explicit StackNode(TreeNode *t) : node(t), visited(false) {}

  ~StackNode() {
    delete node;
  }

  private:
  StackNode(const StackNode &);
  StackNode operator=(const StackNode &);


};

void printAncestor(Tree t, int key) 
{
  std::stack<StackNode *> stack;

  if (!t || t->el == key) return;

  stack.push(new StackNode(t));

  TreeNode *tmp = t->left;

  while (!stack.empty()) {

    if (tmp) {

      if (tmp->el == key) {
        //Key found print the ancestors
        while (!stack.empty()) {
          StackNode *s = stack.top();
          printf("%d ", s->node->el);
          stack.pop();
        }
      } else {
        stack.push(new StackNode(tmp));
        tmp = tmp->left;
      }
    } else {
      //Traverse the right subtree, if not traversed
      StackNode *s = stack.top();
      if (!s->visited) {
        s->visited = true;
        tmp = s->node->right;
      } else {
        stack.pop();
      }
    }
  }

}

Tree newTree() 
{
  TreeNode *root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->left->right = new TreeNode(5);
  root->right->left = new TreeNode(6);
  root->right->right = new TreeNode(7);
  root->left->left->left = new TreeNode(8);
  root->left->right->right = new TreeNode(9);
  root->right->right->left = new TreeNode(10);

  return root;
}

int main(int argc, char const *argv[])
{
  Tree t  = newTree();

  for (int i = 1; i <= 11; ++i) {
    printf("%d: ", i);
    printAncestor(t, i);
    printf("\n");
  }
  
  return 0;
}

Advertisements