How to validate a Binary Tree?

Question

I have been doing some digging around Binary Tree and Binary Source Tree. Ran into this very fundamental question of the Tree (BT) and challenges the properties of a Binary Tree to be proven.

---

Question: Given a node (the root), check if this is a valid Binary Tree. Not asking to validate if given BT is a BST, but simply asking to check if below is a BT.

Valid:
  X1
 /  \
X4   X5
 \    \
  X3   X7

Invalid:
  X1
 /  \
X4   X5
 \  /  \
  X3   X7


# A Python class that represents an individual node in a BT
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key 

    def isNotBinaryTree(root):
        # code here

if isNotBinaryTree(root):
   print "True"
else: 
   print "False"

I do know this is NOT a binary tree (in fact, this is not even a tree by its definition and properties). Thing is... how do I prove or validate this? Or how do I validate this is not a BT where x4 and x5 -> x3 (multiple parent (nodes) point to a same child node? ***No data provided! What would the algorithm/logic look like if I were to solve this? (Python x.x preferred)

Answer 1

Given your data structure, it should be pretty easy to take a node and recursively see if there's a cycle with a simple function like:

def hasCycle(node, seen = set()):
    if node in seen: return True
    seen.add(node)
    if node.left and hasCycle(node.left, seen): 
        return True
    if node.right and hasCycle(node.right, seen): 
        return True
    return False

This just does a depth first search and keeps a set of nodes visited. If you see a node twice, that's a cycle.