Leetcode #331. Verify Preorder Serialization of a Binary Tree

isValidSerialization.cpp

class Solution {
public:
    /*
        Intuition:
        1) every node has to be a left or right child of some node, except the root ofcourse
        2) every non "#" node means it has 2 leaves so a valid preorder string would have 2 more values
        3) Using 1 and 2, set totalnodes = 0. Add 2 to totalnodes if non "#" value encountered and decrement totalnodes for                  having processed present value
        4) Using this scheme, totalnodes should equal 0 at end if it's a valid preorder string.
        5) We start with totalnodes = 1 instead of 0 cause inside loop it does totalnodes-- for every value , which includes
           root value as well.
    */
    
    bool isValidSerialization(string preorder) {
        stringstream ss(preorder);
        string nodevalue;
        
        int totalnodes = 1;
        
        while(getline(ss, nodevalue, ',')){
            totalnodes--;
            
            if(totalnodes < 0) return false;
            if(nodevalue != "#") totalnodes += 2;    
        }
        
        return totalnodes == 0;
    }
};