Populate the data field of all the nodes of the tree

0
votes

A node of a binary tree has two pointers, 'left' and 'right', and two data fields, 'leftcount' and 'rightcount'. 'leftcount' specifies the number of nodes in the left subtree of the node, and 'rightcount' specifies the number of nodes in the right subtree of the node. Write an algorithm to populate the data fields of all the nodes of the tree.

I was asked this question in an interview. I came up with a solution which was based on a postorder traversal of the tree. Can someone please guide me on this.

1
algorithmdata-structurestree
If you already have a solution, then what is your question for the SO audience? – Oliver Charlesworth
@OliCharlesworth : Thanks for your reply. I have put this post as I was asked if I can do it any other way that I proposed. – user1225752

1 Answers

1
votes

This should work (I believe):

int populateCounters(Node* node) {
    if(node == NULL) return 0;
    node->leftCount = populateCounters(node->left);
    node->rightCount = populateCounters(node->right);
    return node->leftCount + node->rightCount + 1;
}