This weekend I completed the data structures portion of the Cracking the Coding Interview Questions on HackerRank. There are a couple of data structurer programming challenges I want to mention, because they opened my eyes to new and interesting ways to solve the problem and/or helped me realize the error of my ways.
One of the programming challenges was verifying that a binary search tree is valid. I smiled with confidence when I first saw the problem, because I thought I knew how to validate a binary search tree. I thought it was nothing more than visiting each node in the binary tree and verifying that the value of the node was greater than its left child and smaller than its right child. One can simply do a depth-first search or breadth-first search to verify this and return
False whenever the value of the node breaks this condition. Turns out this is a common mistake, and I fell for it.
Validating Binary Search Tree
The trick to validating a binary search tree is to keep track of a minimum and maximum range of values for each node. Set these minimum and maximum values accordingly as you visit each node in the binary tree and make sure the value of the node is within those bounds. Here is the Python code I used in the programming challenge to validate a binary search tree. Well, not exactly the same, because I wrote it again from scratch for more practice, but the algorithm is the same.
def is_binary_search_tree(root): def is_bst(node, min, max): if node.key <= min: return False if node.key >= max: return False left_ok = True right_ok = True if node.left is not None: left_ok = is_bst(node.left, min, node.key) if node.right is not None: right_ok = is_bst(node.right, node.key, max) return left_ok and right_ok if root is None: return True return is_bst(root, float('-inf'), float('inf'))
In the beginning I set the
max values to minus and plus infinity, because the root can be any value. However, its left child has to be less than its value (max = node.key) and its right child has to be greater than its value (min = node.key). These
max values continue to change accordingly as you visit every node in the tree. It's crazy obvious and I feel enlightened now that I realize this.
Create Binary Search Tree in Python and Validate It
If I take some code from a previous article, Inorder Traversal of Binary Search Tree in Python, to build and display the binary search tree, we can verify this does indeed validate a binary search tree. Here is some code that creates a binary search tree in Python using level-order traversal and node values provided in a specific order. There is also a
display_nodes function that does an inorder traversal of the binary search tree, displaying the value of each node. Note: I really need to create a better solution for creating a binary search tree, but this will do for now.
from collections import deque class Node: def __init__(self, key): self.key = key self.left = None self.right = None def add(node, root): if root is None: raise ValueError('root cannot be None.') nodes_found = deque([root]) while len(nodes_found) > 0: current_node = nodes_found.popleft() if current_node.left is None: current_node.left = node break if current_node.right is None: current_node.right = node break nodes_found.append(current_node.left) nodes_found.append(current_node.right) def is_binary_search_tree(root): def is_bst(node, min, max): if node.key <= min: return False if node.key >= max: return False left_ok = True right_ok = True if node.left is not None: left_ok = is_bst(node.left, min, node.key) if node.right is not None: right_ok = is_bst(node.right, node.key, max) return left_ok and right_ok if root is None: return True return is_bst(root, float('-inf'), float('inf')) def display_nodes(root): if root is None: return if root.left is not None: display_nodes(root.left) print(root.key, end=' ') if root.right is not None: display_nodes(root.right) root = Node(8) keys = [4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15] for key in keys: add(Node(key), root) print(is_binary_search_tree(root)) # True display_nodes(root) # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
You can experiment with different node values to break the binary search tree. For example, I can replace 6 with 16 and this should return
False, because this is no longer a valid binary search tree. Sixteen is greater than 2, but it cannot be greater than the root node 8.
root = Node(8) keys = [4, 12, 2, 16, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15] for key in keys: add(Node(key), root) print(is_binary_search_tree(root)) # False display_nodes(root) # 1 2 3 4 5 16 7 8 9 10 11 12 13 14 15
There are a lot of really cool programming challenges in the Cracking the Coding Interview Questions on HackerRank. Validating a binary search tree was a particularly interesting programming challenge to me, because I thought I clearly knew the answer. Turns out I was totally wrong and making a common mistake. Hope you found this useful. You can catch me on twitter as @KoderDojo.