A Binary Search Tree (BST) is a special type of binary tree that follows two properties:
All the left child nodes have a smaller value than their parent node
All the right child nodes have greater value than their parent node
So, for each node, it either misses a child node or has a smaller node on the left and a larger node on the right.
A binary search tree with 8 nodes
This property is especially useful for searching elements in a binary tree. If we’re looking for a value x, this way we always know which way to go to find that value. In the example presented above, to find the node with value 3, we can first look at the root node with value 5. As 5 is greater than 3, we move left. We then look at the node with the value 2, and as 2 is smaller than 3, we move right. We then look at the node with the value 4, and as 4 is greater than 3, we move left. We then look at the node with the value 3, and as 3 is equal to 3, it means that we found the node.
# Assume that non-existing nodes are None instead of having a value of 0
def search(node: Node | None, x: int):
""" Return True if `x` is present in the tree and False otherwise """
if node is None: # If we've reached the end of the tree
return False # We didn't find the value `x`
if x == node.value: # If `x` is equal to `node.value`
return True # => we found the value `x` in the tree
if x < node.value: # If `x` is smaller => we need to move left
return search(node.left) # Try to find `x` in the left subtree
return search(node.right) # Otherwise try finding `x` in the right one
This way of searching can be very efficient if the height of the tree is small enough. On each iteration we either move to the left or the right subtree, so searching in this binary search tree would result in the number of operations being equivalent to the height of the tree in the worst-case scenario.
Challenge: Check if the given tree is a BST
Given a binary tree, you are asked to check if it’s a binary search tree.
Input
The input contains space-separated integers representing the values in the nodes of the binary tree. The order of the values is given by traversing from the left to the right subtree every time. A value of 0 means that the node does not exist. It’s guaranteed that the input binary tree is valid and the values are unique.
Output
The program should print Yes if the binary tree is a binary search tree, and No otherwise.
Examples
Input
Output
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0
No
5 2 7 1 4 0 0 3 0 0 0 6 8 0 0 0 0
Yes
Explanation
Example 1: Even though all the right child nodes are greater than the parent nodes, not all left children are smaller than their parent.
Example 2: It’s a binary tree as all the left child nodes have smaller values than their parent, while all the right child nodes have a greater value than their parent.
.png?table=block&id=d38f3a2d-e475-4f6c-bea3-73bcad367966&cache=v2)
