Binary Search Tree (BST)
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.
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.
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.
The program should print
Yesif the binary tree is a binary search tree, and
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0
5 2 7 1 4 0 0 3 0 0 0 6 8 0 0 0 0
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.
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB