C# | Using Stack | O(N) Time Complexity & O(N) Space Complexity | Simple Solution
Intuition\nI was initially thinking of using a DFS or building a tree but wanted to do a better to handle this, so came up with an O(N) approach that uses stack
# Intuition\nI was initially thinking of using a DFS or building a tree but wanted to do a better to handle this, so came up with an O(N) approach that uses stack to solve this problem\n\n# Approach\nWill be using a stack to keep track on which direction we are moving, as we have only two directions left and right, I am using boolean to indicate this. \nTrue mean moving left \nFalse mean moving right \n\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```csharp []\npublic class Solution {\n    public bool IsValidSerialization(string preorder) {\n        //base condition\n        if (preorder == "" || preorder.Length == 0 || (preorder.Length == 1 && preorder[0] == \'#\'))\n        {\n            return true;\n        }\n        //if we are starting with null, that means its not valid\n        if (preorder[0] == \'#\')\n        {\n            return false;\n        }\n        Stack<bool> stack = new Stack<bool>(); //int this is direction\n        //true means left \n        //false mean right\n        stack.Push(true);\n        var start = 0;\n\n        while (start < preorder.Length && preorder[start] != \',\')\n        {\n            start++;\n        }\n        start++;//default we are considering the initial node as parent and moving left for it\n        for (var i = start; i < preorder.Length; i++)\n        {\n            while (i < preorder.Length && preorder[i] != \',\')\n            {\n                i++;\n            }\n            if (stack.Count == 0) //if we are not left with any parent then its not valid any more\n            {\n                return false;\n            }\n            if (preorder[i - 1] == \'#\')\n            {\n                while (stack.Any())\n                {\n                    var direciton = stack.Pop();\n                    if (direciton) //if we are moving left then now left move right\n                    {\n                        stack.Push(false);\n                        break;\n                    }\n                    //if we are already moving right then we have to remove this and check for its parent\n                }\n            }\n            else\n            {\n                stack.Push(true); //if not hash for newly inserted node we should go left\n            }\n        }\n        return stack.Count == 0; //after all operations stack should be empty else its not valid\n    }\n}\n```
['C#']