# create sorted vector of content of two binary search trees in sorted order

You are given two binary search trees, the goal is produce a sorted array of elements containing elements from both the trees.

I wanted to know if there is a simpler approach, and if the use of boost variant is justified in the code. The code uses a stack to iterate over the binary search tree. The stack maintains the state for pre-order traversal of the tree.

#include <iostream>
#include <stack>
#include <boost/range/irange.hpp>
#include <boost/variant.hpp>
#include <random>
#include <algorithm>

using namespace std;
using  boost::irange;
using boost::variant;

struct Node
{
Node(Node* l, Node* r, int v):left(l), right(r), val(v)
{

}
Node* left;
Node* right;
int val;
};

typedef variant<Node*, int> stkElemT;
typedef stack<stkElemT> bstStkT;

//from variant extract the pointer if valid otherwise NULL
struct stkElemVisitorNode : public boost::static_visitor<Node*>
{
Node* operator()(const int& val) const { return NULL; }
Node* operator()(Node*& ptr) const {  return ptr; }
};

//from variant extract the integer value if valid otherwise -1
struct stkElemVisitorInt : public boost::static_visitor<int>
{
int operator()(const int& val) const { return val; }
int operator()(Node*& ptr) const { return -1; }
};

//expand left most path of top node.
void fillPathStkRecurse(bstStkT& bstStk)
{
stkElemT topE = bstStk.top();

Node* topN = boost::apply_visitor(stkElemVisitorNode(),  topE);
if(topN != NULL) //
{
bstStk.pop();
if (topN->right)
bstStk.push(topN->right);
bstStk.push(topN->val);
if (topN->left)
{
bstStk.push(topN->left);
}
fillPathStkRecurse(bstStk);
}
else{
return; //top node is not a pointer but  value
}
}

int getTopVal(const bstStkT& bstStk)
{
assert(!bstStk.empty());
stkElemT topE = bstStk.top();
int val  = boost::apply_visitor(stkElemVisitorInt(),  topE);
return val;
}

void incrBstStk(bstStkT& bstStk)
{
if(bstStk.empty()) return;
int topVal = getTopVal(bstStk);
assert(topVal != -1);
bstStk.pop();
if(!bstStk.empty())
fillPathStkRecurse(bstStk); //expand till child node
return;
}

Node* create_tree(vector<int>& vals, int start, int end) //end excluded
{
if(end==start)
return new Node(NULL, NULL, vals[start]);

if(end == start + 1)
{
Node* curr = new Node(NULL, NULL, vals[start]);
curr->right = new Node(NULL, NULL, vals[start+1]);
return curr;
}

int mid = floor((start + end)/2.0);

Node* left = create_tree(vals, start, mid-1);
Node* right = create_tree(vals, mid+1, end);
Node* curr = new Node(left, right, vals[mid]);
return curr;
}

vector<int> merge_bst(Node* root1, Node* root2)
{
vector<int> res;
bstStkT bstStk1;
bstStk1.push(root1);
fillPathStkRecurse(bstStk1);

bstStkT bstStk2;
bstStk2.push(root2);
fillPathStkRecurse(bstStk2);

while(1)
{
//cout<<"stk sizes = "<<bstStk1.size()<<" "<<bstStk2.size()<<endl;
if(bstStk1.empty() && bstStk2.empty())
break;

int val1 = numeric_limits<int>::max();
if(!bstStk1.empty())
val1 = getTopVal(bstStk1);

int val2 = numeric_limits<int>::max();
if(!bstStk2.empty())
val2 = getTopVal(bstStk2);

if(val1 <  val2)//consume bstStk1
{
res.push_back(val1);
incrBstStk(bstStk1);
}
else
{
res.push_back(val2);
incrBstStk(bstStk2);
}
}
return res;
}

int main(int argc, char** argv)
{
std::mt19937 rng;
rng.seed(std::random_device()());
std::uniform_int_distribution<std::mt19937::result_type> uid5k(0, 1000); // distribution in range [1, 6]

int n = 10000;
for(auto k: irange(0, 10000))
{
vector<int> inVec1;
for(auto i: irange(0, n))
inVec1.push_back(uid5k(rng));

sort(inVec1.begin(), inVec1.end());
Node* root1 = create_tree(inVec1, 0, n-1);

vector<int> inVec2;
for(auto i: irange(0, n))
inVec2.push_back(uid5k(rng));
sort(inVec2.begin(), inVec2.end());
Node* root2 = create_tree(inVec2, 0, n-1);

vector<int> merged_vec(inVec1.begin(), inVec1.end());
merged_vec.insert(end(merged_vec), begin(inVec2), end(inVec2));
sort(begin(merged_vec), end(merged_vec));

auto res = merge_bst(root1, root2);
assert(res == merged_vec);
}

return 0;
}

• Take a look at lines 90 to 93. This is a great example why you should never omit braces. – yuri Jul 21 '18 at 14:01
• Good catch. Have fixed it. – Sandeep Jul 21 '18 at 14:25
• @Sandeep, I couldn't compile it on wandbox. Does it compile on your machine? If so, could you please specify what tool-chain are you using? – Incomputable Jul 21 '18 at 14:58
• I am using g++ 7.3 on Fedora with no flags. It does have dependency on boost. – Sandeep Jul 21 '18 at 15:18
• Your title says the goal is to print the combined values, but your post says you just want to create an array. Is it both or one or the other? – tinstaafl Jul 21 '18 at 23:40

## Design

If you are going to do this the C++ way then you should be using standard algorithms. A tree is a type of container; so you should be able to get an iterator to logically pass over each element in the container.

As a result I would expect the code to look like this:

    Tree    one;
Tree    two;
// Add data to one and two here.

std::vector<int> result;
result.reserve(one.size() + two.size());

// There is a standard algorithm to combine two sorted containers.
// So I would expect you to use that. Which means your
// Tree structure should support an iterator concept.
std::merge(std::begin(one), std::end(one),
std::begin(two), std::end(two),
std::back_inserter(result));


So looking at your code I see

struct Node
{
Node* left;
Node* right;
int val;
};


What I would actually expect to see is:

class Tree
{
struct Node
{
Node*   left;
Node*   right;
int     val;
};
class Iterator
{
public:
using   value_type      = int;
using   pointer         = int*;
using   reference       = int&;
using   difference_type = std::ptrdiff_t;
using   iterator_category = std::forward_iterator_tag;

Iterator();       // end()
Iterator(Node*);  // begin()

int const& operator*();
Iterator operator++();
Iterator operator++(int);

bool operator==(Iterator const& rhs) const;
bool operator!=(Iterator const& rhs) const;
};
Node*        root;
std::size_t  size;

public:
Tree();
void insert(int val);

using iterator       = void;      // can't modify a BST
using const_iterator = Iterator;

const_iterator begin()  const {return Iterator(root);}
const_iterator cbegin() const {return Iterator(root);}
const_iterator end()    const {return Iterator();}
const_iterator cend()   const {return Iterator();}

bool         empty() const;
std::size_t  size()  const;
};


## Code Review

Now that I have shown what I would expect, let's have a look at what you wrote.

### Don't use the using namespace X expression.

Doing this is bad practice. You are asking for trouble in the long run. For details see: Why is “using namespace std” considered bad practice?

using namespace std;


Even doing the below can be dangerous (though less than above). If you are going to do this don't do it at file scope: try and restrict the scope by doing it inside a function.

using boost::irange;
using boost::variant;


Both of these are bad habits. So, even for small projects, you should resist doing this. Habits are hard to break and you may do it accidentally when it actually matters.

The reason the "Standard" namespace is called "std" is so that the prefix std:: did not impose a large burden.

### Constructor Using brace list

In this type of simple case:

struct Node
{
Node(Node* l, Node* r, int v):left(l), right(r), val(v)
{

}
Node* left;
Node* right;
int val;
};


You don't actually need to define a constructor. You can use brace initialization to initialize all the members (without needing a constructor).

Node x = new Node {nullptr, nullptr, 3};


### User Defined Types

Its normal to use an initial capitol letter to define "User Defined Types" (while functions and variables have an initial lower case letter).

Now this is a common convention, but not universal (so you can take it or leave it). But using this convention does help. One of the big things about C++ is the type information. Being able to distinguish types from objects is really useful (so its a convention I follow).

typedef variant<Node*, int> stkElemT; // I would use StkElemT (see next rule)
typedef stack<stkElemT> bstStkT;      // I would use BstStkT  (see next rule)


### Self Documenting Code

Writing self documenting code is critical to writing maintainable code. This basically means writing function and type names that explain exactly what they do.

typedef variant<Node*, int> stkElemT; // I would use StackElement
typedef stack<stkElemT> bstStkT;      // I would use SearchTreeStack


I actually like your comments (I usually hate people's comments). These are actually useful. So keep this up.

//from variant extract the pointer if valid otherwise NULL
struct stkElemVisitorNode : public boost::static_visitor<Node*>

//from variant extract the integer value if valid otherwise -1
struct stkElemVisitorInt : public boost::static_visitor<int>

//expand left most path of top node.
void fillPathStkRecurse(bstStkT& bstStk)
{
}


### BST and Balanced BST

A BST (binary search tree) does not need to be balanced. You go to extensive lengths to make sure the tree you build is balanced. I think this is overkill. A simple BST is easier to build.

Node* create_tree(vector<int>& vals, int start, int end) //end excluded


### Begin/End

In C++ it is more traditional for the end iterator to be one past the end. Your code it marks the actual last element.

Its a valid choice. But not traditional C++ (so you should mention it in the comment. You try but I am not sure its clear). I would also encourage you to try it using the traditional method; in my opinion it will make the code easier.

Node* create_tree(vector<int>& vals, int start, int end) //end excluded


### Prefer nullptr over NULL

    return new Node(NULL, NULL, vals[start]);


In C++11 we introduced nullptr which is a type safe NULL.

• Thank you for your generous time for review. Its spot on and hope it helps others like me as well. – Sandeep Jul 25 '18 at 1:21
• I am ruined by Python :), so have bit of hesistation in writing iterators in c++. I do agree with this. In fact the motivation was to follow iterator paradigm but didn't go as far as modeling as C++ iterator. – Sandeep Jul 25 '18 at 1:25