✅ Verify Preorder Serialization of a Binary Tree | How Many Slots Are Available?
Solution 1:\n\nExplanation:\nLet us first try to understand the meaning of "Slot",\nSlot is an empty place where we can put the TreeNode,\n\nNow why we are deal
**Solution 1:**\n```\nExplanation:\nLet us first try to understand the meaning of "Slot",\nSlot is an empty place where we can put the TreeNode,\n\nNow why we are dealing with Slots??\nAs we want to verify whether the preorder serialization is correct or not!,\nso we want to confirm whether the number of TreeNodes(including nullable nodes \'#\') are equal to NumberOfSlotsAvailable in Tree,\ni.e, Number Of TreeNodes == Number Of Slots Available (Valid Preorder Serialization)\nelse Invalid Preorder Serialization.\n\nNow Let us see that how we can calculate the number of slots,\n1) For a Leaf Node (0 Children) the slots will be 1 (Why because that slot is only for that leaf node).\n2) For a Non Leaf Node the slots will be 3 ,\nHOW??\n1 slot for the non leaf node itself,\n2 slots for its Left and Rigth Child,\n\n3) And for Nullable Node(\'#\') the slots will be 1,\nwhy??\nbecause if a node is NULL then its parent has to define a pointer (NULL) to mention that\neither its left or right child is NULL.\n\nLets take One Example:\n"9,3,4,#,#,1,#,#,2,#,6,#,#"\n\nInitially The numberOfSlots = 1 (To accomodate root node only)\n\n1) when we encounter 9 ,\nwe decrease the numberOfSlots by 1 (because the node 9 is now placed at that slot)\nso numberOfSlots become 0\nnow we will check whether this node is Non Leaf Node,(if it is != \'#\'),\nso as 9 is non leaf node,\nso we add 2 in the numberOfSlots(2 slots for its children)\nnow numberOfSlots become 2\n\n2) Similarly for "3",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 1)\n--> Then increment numberOfSlots by 2 (numberOfSlots = 3)\n\n3) Similarly for "4",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 2)\n--> Then increment numberOfSlots by 2 (numberOfSlots = 4)\n\n4) For "#",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 3)\n--> As this is Nullable Node so we don\'t increment the numberOfSlots\n\n5) again  For "#",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 2)\n--> As this is Nullable Node so we don\'t increment the numberOfSlots\n\n6) Similarly for "1",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 1)\n--> Then increment numberOfSlots by 2 (numberOfSlots = 3)\n\n7) again  For "#",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 2)\n--> As this is Nullable Node so we don\'t increment the numberOfSlots\n\n8) again  For "#",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 1)\n--> As this is Nullable Node so we don\'t increment the numberOfSlots\n\n9)Similarly for "2",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 0)\n--> Then increment numberOfSlots by 2 (numberOfSlots = 2)\n\n10) again  For "#",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 1)\n--> As this is Nullable Node so we don\'t increment the numberOfSlots\n\n11) Similarly for "6",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 0)\n--> Then increment numberOfSlots by 2 (numberOfSlots = 2)\n\n12) again  For "#",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 1)\n--> As this is Nullable Node so we don\'t increment the numberOfSlots\n\n13) again  For "#",\n--> First we decrement numberOfSlots by 1. (numberOfSlots = 0)\n--> As this is Nullable Node so we don\'t increment the numberOfSlots\n\nAnd finally compare whether numberOfSlots == 0 (If Yes) return true else return false;\n\n```\n\n***\nC++:\n```\nclass Solution {\npublic:\n    bool isValidSerialization(string preorder) \n    {\n        stringstream ss(preorder);\n        string temp;\n//      For Root Node\n        int numberOfSlotsAvailable = 1;\n        while(getline(ss,temp,\',\'))\n        {\n//          When we put one node into the empty slot\n            numberOfSlotsAvailable--;\n            if(numberOfSlotsAvailable<0)\n                return false;\n            if(temp!="#")\n            {\n//                 It means we already put the Non Leaf Node and there are new 2 slots being created for left and right child.\n                numberOfSlotsAvailable+=2;\n            }\n        }\n        return numberOfSlotsAvailable==0;\n    }\n};\n```
[]