CODEWITHSUNDEEP
c++recursiontreemachine-learningtree-balancing
davidhigh
davidhigh

Reputation: 15468

C++ balanced tree / call order in recursive function

I'm writing an implementation of a CART tree at the moment, which is binary tree used in machine learning. It is trained recursively as sketched in the following code:

struct Node
{
    Node * parent;
    Node * left;
    Node * right;
};

void train(Node* node)
{
    //perform training algorithm on node

    train(node->left);
    train(node->right);
}

Now assume I restrict the number of traing iterations to a chosen value, say nTraining=4.

Then, by unrolling the recursive function calls, I expect that only the left branch is evolved. So the first four calls are:

    train(node);
    train(node->left);
    train(node->left->left);
    train(node->left->left->left);
    //only now train(node->left->left->right); would follow

which gives a completely unbalanced tree looking like

          O
         / \
        O   O
       / \
      O   O
     / \
    O   O
   / \
  O   O

Can anybody please suggest a way by which I can further use the recursive training approach and still obtain a balanced tree?

Upvotes: 0

Views: 475

Answers (1)

Anton Savin
Anton Savin

Reputation: 41301

I'd say, don't use recursion (DFS). Use BFS, that is queue instead, so the tree is traversed level by level:

std::queue<Node*> q;
Node* root;
q.push(root);
for (int i = 0; i < nTraining; ++i) {
    Node* node = q.front();
    q.pop();
    train(node);
    q.push(node->left);
    q.push(node->right);
}

Upvotes: 2

Related Questions