Tail recursion of the level order traversal using a predefined function signature

Willi 0
Viewed 40

my question is how to use tail recursion to traverse the binary tree in the level order and print it in a specific format.

Binary Tree
          __ 60 _ 
         |        |
      __ 50 _     100 _ 
     |       |         |
     30      55        1000 

output  "60 : 50, 100 : 30, 55, 1000"

my code snippet and it works:

void LevelOrderTraversalTailRecur(BinaryTreeNode* root, int level, vector<vector<int>>& vec) {
    if (root == nullptr) return;
    
    if (vec.size() < level) {
        auto v{std::vector<int>{}};
        vec.push_back(v);
    }

    vec[level - 1].push_back(root->data);

    if (root->left != nullptr) {
        LevelOrderTraversalTailRecur(root->left, level+1, vec);
    }

    if (root->right != nullptr) {
        LevelOrderTraversalTailRecur(root->right, level+1, vec);
    } 
}

void LevelOrderTraversal(BinaryTreeNode* root) {
    if (root == nullptr) {
        cout << "null";
        return; 
    }
    std::vector<std::vector<int>> vec;
    LevelOrderTraversalTailRecur(root, 1, vec); 
    // ....
    // convert the vector into a string
}

But I would like to use the interface void LevelOrderTraversalTailRecur(BinaryTreeNode* root, int level, string &s) directly instead of vector<vector>. How can I achieve it?

Thanks!

tail-recursion algorithm c++
1 Answers

A common way of implementing a level-order traversal is to store all tree nodes belonging to a level in a vector, and then iteratively descending a level.

void LevelOrderTraversal(BinaryTreeNode* root) {
  int level = 1;
  std::vector<BinaryTreeNode*> pending = { root };
  while (!pending.empty()) {
    // Produce the requested output
    auto it = pending.cbegin();
    if (level > 1) std::cout << ": ";
    std::cout << it->data;
    for (; it != pending.cend(); it++) {
      std::cout << ", " << it->data;
    }

    std::vector<BinaryTreeNode*> next;
    for (auto node : pending) {
      if (node->left)  next.push_back(node->left);
      if (node->right) next.push_back(node->right);
    }
    std::swap(pending, next);
    level++;
  }
Botje0
Related