We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Trees: Is This a Binary Search Tree?
  2. Discussions

Trees: Is This a Binary Search Tree?

  • newbier
     + 0 comments
    • Python 3
    • an in order traversal of the tree and save the order indexes into data_list
    • set new property ancestor into node objects, which is somewhat cheating because may only be add in dynamic language such as Python, but can also be implement in other static languages by using data structure like dictionaries / hashmaps
    • check data_list is in order, and also no duplication (by checking length)
    from collections import defaultdict

def checkBST(root):
    node_traversed_counts = defaultdict(int)
    current_node = root
    current_node.ancestor = None
    data_list = []
    while node_traversed_counts[root] < 3:
        # new node
        if not node_traversed_counts.get(current_node):
            node_traversed_counts[current_node] += 1
            
            # is leaf node
            if not current_node.left and not current_node.right:
                data_list.append(current_node.data)
                current_node = current_node.ancestor
            # is not leaf node
            else:
                if current_node.left:
                    current_node.left.ancestor = current_node
                    current_node = current_node.left
        # node having been traversed before
        else:
            node_traversed_counts[current_node] += 1
            if node_traversed_counts[current_node] == 2:   
                data_list.append(current_node.data)
                if current_node.right:
                    current_node.right.ancestor = current_node
                    current_node = current_node.right
                    continue
            current_node = current_node.ancestor
    return data_list == sorted(data_list) and len(set(data_list)) == len(data_list)