CODEWITHSUNDEEP
c++
user7922379
user7922379

Reputation:

Explanation of this condition in binary tree

I found a program online that traverses a binary tree in level order. The code below passes and produces the desired output: 

class Solution {
public:

    std::vector< vector< int >> res;

    void buildVec(TreeNode* root, int level) {
        if(root==NULL)
            return;
        if(res.size()==level)
            res.push_back(vector< int >());

        res[level].push_back(root->val);
        buildVec(root->left, level+1);
        buildVec(root->right, level+1);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        res.clear();
        buildVec(root, 0);
        return res;
    }
};

What I don't understand is the statement: if(res.size()==level). What exactly does this statement achieve? When the level is 2, there can be (at max) 4 elements (since levels start with 0), which is greater than the value of label (2). So, how does this statement work?

Edit: So, if the input is:

   3
 /  \
9   20
   /  \
  15   7

then the output returned would be 

[
   [3],
   [9,20],
   [15,7],
]

Upvotes: 1

Views: 49

Answers (2)

Corristo
Corristo

Reputation: 5520

The reason it is there is to avoid having the second recursive call to buildVec add another level-vector to the end of the result vector, even though the first call already added one for this particular level.

It is easiest to figure out what is going on by doing an example run on your example tree without 15 and 7.

The first thing levelOrder does is empty the res vector. Then it calls buildVec(root, 0). In there root isn't equal to NULL, but it holds res.size() = 0 = level, so an empty vector gets appended to res, thus res = [[]]. In the next step the value of the current node is pushed into the newly appended vector. So res = [[3]].

Then buildVec(root->left, 1) is called. There, again root isn't NULL but res.size() = 1 = level, so another empty vector is appended to res, therefore res = [[3], []]. We insert the value 9 into res[1], so now res = [[3], [9]].

When calling buildVec(root->left, 2) and buildVec(root->right, 2) nothing happens because both children don't exist, i.e. in these calls root == NULL returns true.

So we continue with the call buildVec(root->right, 1). Here, for the first time, res.size() = 2 != 1 = level. So we don't append a new vector. Then we insert the value 20 into res[1]. So res = [[3], [9, 20]].

Were the check res.size() == level not there, we would've appended a new empty vector at the end, so the result would've been res = [[3], [9, 20], []] instead.

But as it turns out, the check is incorrect. If you flip the tree to 

     3
   /   \
  20    9
 / \
15  7

it will return [[3], [20, 9], [15, 7], []]. The correct check is res.size() <= level.

Upvotes: 1

Rajeev Singh
Rajeev Singh

Reputation: 3332

if(res.size()==level)
    res.push_back(vector< int >());

This statement is just to add another vector into the res for a new level.

  3
 /  \
9   20
   /  \
  15   7

Let's take for node 15 the level will be 2.

the value of res will be [[3], [9, 20]] and res.size() == 2, condition will be true, so it will create a new vector for new level and insert the node 15 in it, again for node 7 the condition will be false since the res.size() will become 3 so the node will be inserted in the res[level] vector without creating the new vector.

Upvotes: 0

Related Questions