Question

Implement a function that returns all the items in a binary search tree in order inside a std::vector. Use the following class and function definition:

class BTNode {
public:
   int item;
   BTNode *left;
   BTNode *right;
   BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){}
};

BTNode *root = nullptr;

std::vector<int> inorder_traversal(BTNode *node) {
     // implement
}

If the BST has no values, return a vector with no items in it.

#include <iostream>
#include <vector>

class BTNode {
public:
int item;
BTNode *left;
BTNode *right;
BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){}
};

BTNode *root = nullptr;

std::vector<int> inorder_traversal(BTNode *node) {
// implement
}

int main()
{
root = new BTNode(10, new BTNode(0), new BTNode(100));

std::vector<int> res = inorder_traversal(root);

for(auto &i : res) {
std::cout << i << ", ";
}
std::cout << std::endl;


return 0;
}

Answer 1

#include <iostream>
#include <vector>

class BTNode {
public:
        int item;
        BTNode *left;
        BTNode *right;
        BTNode(int i, BTNode *l = nullptr, BTNode *r = nullptr): item(i), left(l), right(r) {}
};

BTNode *root = nullptr;

void help_recursive_inorder(BTNode* node,std::vector<int> &result)
{
    // Recursive implementation of inorder traversal of BST
        if (node == nullptr)
                return;
        help_recursive_inorder(node->left, result);
        result.push_back(node->item);
        help_recursive_inorder(node->right, result);
}
std::vector<int> inorder_traversal(BTNode *node) {
        std::vector<int> result;//Final result is stored in result variable of type vector.
        help_recursive_inorder(node, result);
        return result;
}

int main()
{
    BTNode* left=new BTNode(2, new BTNode(1), new BTNode(3));
    BTNode* right=new BTNode(6, new BTNode(5), new BTNode(7));
        root = new BTNode(4,left, right);
        std::vector<int> res = inorder_traversal(root);
        for (auto &i : res) {
                std::cout << i << ", ";
        }
        std::cout << std::endl;
        return 0;
}