Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation

  • Binary Search Tree (BST)

    A Binary Search Tree (BST) is a special type of binary tree that follows two properties:
    1. All the left child nodes have a smaller value than their parent node
    1. 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
    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.
    notion image
    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.
    notion image
     
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue