You know is not valid when children are connected. (Then is a graph) Pseudocode. Node node{ id; node right; node left; } Main{ ids = [] traverse(Node node){ if node.id in ids: -not valid else: ids.push(node.ids) if node.right != null: traverse(node.right) if node.left != null traverse(node.left) } }