My codingforinterviews task

gistfile1.md

Explain what a binary search tree is and what to consider when implementing one.

Binary search tree (BST) can be represented by a linked data structure. Each node contains key value, data and references to left and right subtree. BST has following properties:

1. Left subtree of a node contains only nodes with keys less than the node's key.
2. Right subtree of a node contains only ondes with keys greater than the node's key.
3. Left and Right subtrees are also binary search trees.

Performance of this data structure depends on heihgt of tree. For perfect balanced tree basic operations run in O(ln n) time. If the tree is a linear chain on n nodes (linked list), the same operations take O(n) time. So when you want implement effective BST you need keep them balanced, so the search will be faster.

Write a function that returns whether a given binary tree is a valid binary search tree

example in Python:

def is_bst(node, min_value, max_value):
    """Validate binary search tree. Function traverses all nodes and 
    check the current node whether BST properties satisfied.
    
    Parameters
    ----------
    node: binary serch tree;    
    min_value: min posible key value;    
    max_value:  max posible key value;   
    """
    
    if node == None:
        return True
    else : 
        if not(min_value < node.key and node.key <max_value):
            return False
        if not is_bst(node.left, min_value, node.key):
            return False
        return is_bst(node.right, node.key, max_value)