Java - Stack
\ngiven traversal is preorder means the order will be\n root\n preorder(left subtree)\n preorder(right subtree)\n    \nSimilarly we try to find the tree from gi
\ngiven traversal is preorder means the order will be\n* root\n* preorder(left subtree)\n* preorder(right subtree)\n    \nSimilarly we try to find the tree from given traversal by following above pattern.\nTo do so we can use **stack** here\n\n----------------------------------------------------------------------------------------------\nCreate a node with first value of traversal and add it to stack(here, as of now we haven\'t filled left and right pointers of this node and we have to keep track of it).\n\nIterating through array of traversal \nif :  value is not null\nthen\n* create a node and add it to stack.(here, as of now we haven\'t filled left and right pointers of this node and we have to keep track of it)\n* peek node from stack (it will be the root for the first time)\n* if  : both left and right pointers are filled \n         then \n         ->we pop that node out and we keep doing this until we find a node which has been not filled with left or right pointer(while loop)\n         ->doing so if stack becomes empty then the given traversal is not valid : return false\n          ->As we are here then it means that there is a valid node that has not been filled with either of let or right pointer\n          ->check if : left is not filled\n                   then\n                        -->create a new new_node\n                        -->fill it to the node.left\n                       -->mark that node\'s left is filled\n                        -->and push new_node to stack\n                    else\n                        -->create a new new_node\n                        -->fill it to the node.right\n                        -->mark that node\'s right is filled\n                        -->and push new_node to stack\n                        \nelse\n*   the process will be same as above for finding a valid node from stack \n    or \n* stack becomes empty doing so then given traversal is invalid : return false\n   after finding valid node\n    check\n        if its left is not filled\n        then \n            -->node.left=null\n            -->mark that node\'s left is filled\n        else\n            -->node.right=null\n            -->mark that node\'s right is filled\n\t\t\t\n```\nclass TreeNode{\n    TreeNode left,right;\n    String val;\n    \n    //to flag that left,right is added or not\n    boolean l,r;\n    TreeNode(String val){\n        this.val=val;\n        this.left=null;\n        this.right=null;\n        this.l=false;\n        this.r=false;\n    }\n}\nclass Solution {\n    public boolean isValidSerialization(String preorder) {\n        \n        String arr[]=preorder.split(",");\n        \n        Stack<TreeNode> stk=new Stack<TreeNode>();\n        \n        //base cases\n        if(arr[0].equals("#")){\n            if(arr.length==1){\n                return true;\n            }else{\n                return false;\n            }\n        }else{\n            TreeNode node=new TreeNode(arr[0]);\n            stk.push(node);\n        }\n        \n        for(int i=1;i<arr.length;i++){\n            \n            //not possible \n            if(stk.isEmpty())\n                return false;\n            \n            //considering values and null saperately\n            //not null\n            if(!arr[i].equals("#")){\n                //top of the stack\n                TreeNode node=stk.peek();\n                \n                //if both left and right pointers are added\n                //then looking for another node and remove this node\n                while(node.l && node.r){\n                    //finding other node if stack becomes empty that means \n                    //given traversal is invalid\n                    if(!stk.isEmpty()){\n                        node=stk.pop();\n                    }else{\n                        return false;\n                    }\n                }\n                //if left is pointer is already added then cosider right pointer\n                if(node.l){\n                    node.right=new TreeNode(arr[i]);\n                    node.r=true;//flaggin right of node\n                    stk.push(node.right);\n                }else{\n                    //if node is node added to node then we first add new node left side of current node\n                    node.left=new TreeNode(arr[i]);\n                    node.l=true;//flagging left\n                    stk.push(node.left);\n                }\n            }else{\n                //similar to above but if arr[i] is null then no need to add to stack\n                TreeNode node=stk.peek();\n                while(node.l && node.r){\n                    if(!stk.isEmpty()){\n                        node=stk.pop();\n                    }else{\n                        return false;\n                    }\n                }\n                if(node.l){\n                    node.right=null;\n                    node.r=true;\n                }else{\n                    node.left=null;\n                    node.l=true;\n                }\n            }\n        }\n        //lastly checking if all the nodes in stack has been added with left and right then its good otherwise given traversal is not valid.\n        while(!stk.isEmpty()){\n            TreeNode node=stk.pop();\n            if(node.l && node.r)\n                continue;\n            else\n                return false;\n        }\n        return true;\n    }\n}\n```
['Stack', 'Java']