isthisbinary.py

#!/bin/python
""" Using In Order Traversal of a potentially Binary Search Tree to determine if the tree is in fact a Binary Search Tree.
The data value of every node's left subtree must be less than the data value of the node
The data value of every node's right subtree must be greater than the data value of the node
Our definition states that a binary search tree may not have any duplicate values

The method that I am using is create an in order traversal of the tree and compare that to a sorted list of the same node data. If they are the same then the tree is a binary search tree.

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
     a) Pop the top item from stack.
     b) Append the popped item's data value to the in order list, set current = popped_item->right
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
"""
global_data_values_set = set()
# above line creates an empty set to hold every data value as the tree is traversed
visited_nodes_set = set()
# above line creates an empty set to hold a pointer to every node as it is visited to ensure that no node is visited twice.

class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def check_node(n):
    # function assumes that an object of node type is the argument
    in_order_list = []
    stack = []
    current_node = n
    done = False
    while not done:
        if current_node is not None:
            stack.append(current_node)
            current_node = current_node.left
        elif current_node is None and len(stack) != 0:
            current_node = stack.pop()
            if current_node in visited_nodes_set:
                return False
            if current_node.data in global_data_values_set:
                return False
            in_order_list.append(current_node.data)
            global_data_values_set.add(current_node.data)
            visited_nodes_set.add(current_node)
            current_node = current_node.right
        else:
            done = True
    # Next step is to compare the in_order list to a sorted version of same list
    comparison_list = sorted(in_order_list)
    if comparison_list == in_order_list:
        return True
    else:
        return False


def checkBST(root):
    if root is not None:
        return check_node(root)
    else:
        return False