# An easy recursive Java Solution that beats 99.9%

• Traverse the tree by moving iter over the preorder string.
(1) Use a traverse function to move iter, return -1 if invalid.
(2) If s[iter] is '#', it is a leaf node, and we only need to skip it and a comma. So return iter+2.
(3) Else, the node must have a left child and right child, move iter to the start of the left tree by finding the first comma which separate the node and the left tree. If there is no comma, it means there is no left, which is invalid, return -1. Else just traverse the left and right subtree.
(4) After traverse, since we assume all node follow a comma, so iter == preorder.length() +1 means the string is the valid compression of the tree.

``````public class Solution {
public boolean isValidSerialization(String preorder) {
if(preorder == null || preorder.length() == 0) return false;
return traverse(preorder, 0) == preorder.length() + 1;
}

private int traverse(String s, int iter){
if(iter < 0 || iter >= s.length()) return -1; //invalid
if(s.charAt(iter) == '#'){
//leaf node, skip # and a comma
return iter + 2;
}
else{
//a node with two subtree
iter = s.indexOf(',', iter); //skip the value of the node
if(iter == -1) return -1; //a value with out comma means it has no child append, which is wrong
iter++; //skip the comma
iter = traverse(s, iter); //traverse the left subtree
iter = traverse(s, iter); //traverse the right subtree
return iter;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.