A tree is invalid if a node is pointed to more than once (e.g., both the left and right child point to the same node). So, traverse the tree and check for any repeats. You can check for repeats by either marking every node as you traverse it or hashing the node in a hash table.