I wrote C++ code:
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
template <class T>
class TreeNode {
public:
T data;
TreeNode<T> *left, *right;
TreeNode() {
data = {};
left = right = NULL;
}
TreeNode(T data) {
this->data = data;
}
};
template <class T>
class BinaryTree {
public:
TreeNode<T> *root;
vector<T> _largestIndependentSet(TreeNode<T> *root) {
static unordered_map< TreeNode<T>*, vector<T> > table;
if(!root)
return {};
if(table.find(root) != table.end())
return table[root];
vector<T> lis = {}, lis_left = {}, lis_right = {},
lis_nrl_left = {}, lis_nrl_right = {}, lis_nrr_left = {}, lis_nrr_right = {};
// Leaf
if(!root->left && !root->right) {
lis.push_back(root->data);
}else{
if(root->left){
lis_left = _largestIndependentSet(root->left);
lis_nrl_left = _largestIndependentSet(root->left->left);
lis_nrl_right = _largestIndependentSet(root->left->right);
}
if(root->right){
lis_right = _largestIndependentSet(root->right);
lis_nrr_left = _largestIndependentSet(root->right->left);
lis_nrr_right = _largestIndependentSet(root->right->right);
}
if( lis_left.size() + lis_right.size() >
lis_nrl_left.size() + lis_nrl_right.size() +
lis_nrr_left.size() + lis_nrr_right.size() + 1 ){ // don't keep root
lis.insert(lis.end(), lis_left.begin(), lis_left.end());
lis.insert(lis.end(), lis_right.begin(), lis_right.end());
}
else {
lis.insert(lis.end(), lis_nrl_left.begin(), lis_nrl_left.end());
lis.insert(lis.end(), lis_nrl_right.begin(), lis_nrl_right.end());
lis.insert(lis.end(), lis_nrr_left.begin(), lis_nrr_left.end());
lis.insert(lis.end(), lis_nrr_right.begin(), lis_nrr_right.end());
lis.push_back(root->data);
}
}
cout<<"Calculated Results for: "<<root->data<<": ";
for_each(lis.begin(), lis.end(), [](T data) {
cout<<data<<" ";
});
cout<<"\n";
table[root] = lis;
return table[root];
}
void largestIndependentSet() {
vector<T> lis = _largestIndependentSet(this->root);
for_each(lis.begin(), lis.end(), [](T data) {
cout<<data<<" ";
});
}
};
int main() {
BinaryTree<int> bt;
TreeNode<int> *root = new TreeNode<int>(10);
root->left = new TreeNode<int>(7);
root->right = new TreeNode<int>(15);
root->left->left = new TreeNode<int>(9);
root->left->right = new TreeNode<int>(12);
root->right->left = new TreeNode<int>(6);
root->right->right = new TreeNode<int>(11);
root->left->left->left = new TreeNode<int>(20);
root->right->left->right = new TreeNode<int>(5);
root->left->left->left->left = new TreeNode<int>(22);
root->left->left->left->right = new TreeNode<int>(21);
root->right->left->right->left = new TreeNode<int>(4);
root->right->left->right->right = new TreeNode<int>(3);
bt.root = root;
bt.largestIndependentSet();
return 0;
}
I compiled it using g++ 5.4.0 on Cygwin:
g++ binary_tree.cpp -std=c++11
The problem is that the after the recursive function _largestIndependentSet() completes, the last print gives me the correct answer. But after that I get this error: Aborted (core dumped), and the print in largestIndependentSet() doesn't execute.
This is baffling because my logic seems to be correct. What is causing this?
PS: If I compile it with c++14 flag it runs fine o_O:
g++ binary_tree.cpp -std=c++14
Not going into more than two major problems in the posted code.
T-value constructor.largestIndependentSet()The former of these is common, especially for beginners in C++. Make sure you leave nothing with indeterminate value. In this case left and right in the TreeNode(T value) constructor were left indeterminate.
The latter of these, is hugely important. The function largestIndependentSet() claims it was returning a vector, but in reality had no return at all. That, likewise, invokes undefined behavior. From there I can speculate, but note that's all it is: speculation:
Speculation: The compiler happily generated the code that ultimately treated whatever happened to be residing on the activation stack, unset by you, as a std::vector<T>. Of course it is indeterminate gibberish because you never returned an actual object. But the invoke of the non-virtual destructor of std::vector<> certainly doesn't know that, and in so doing, treated whatever happened to be occupying what it thinks are its member variables as valid data, when in reality it was anything but. The short of it is this: take random memory, point std::vector<> destructor code at it, lie to the code and say that memory holds a valid std::vector<> object, then turn the destructor loose.
As to why the compiler didn't error. Well, often in C or C++, it simply isn't an error to do something unwise. The compiler expects you to know enough about what you're doing, and in this case, no language violations were present, so it gave you the benefit of the doubt. However... Turning up your compiler warning levels to pedantic heights will, on most modern compilers (icc, gcc, clang, and msvc for certain) warn you about your missing return value. Those warnings are there for a reason, and I strongly support turning them up and treating them as errors (also a compiler option).