Binary Search Tree

Jan. 26, 2022, 9:47 a.m.

A tree is recursively defined as a set of one or more nodes where one is designated as the root of the tree.
A binary tree is a data structure that is defined as a collection of elements called nodes. In a binary tree, the topmost element is called the root node, and each node has 0, 1 or at the most 2 children.

A binary search tree, also known as an ordered binary tree in which the nodes are arranged in an order.

Binary search tree is a binary tree with the following properties:

1) The left subtree of a node contains values that are less than node value.

2) The right subtree of a node contains values that are greater than node value.

3) Both left and the right binary trees also satisfy these properties.

Inserting a new node in a binary search tree:

# Node
class Node:
    def __init__(self,value):
        self.value = value
        self.right = None
        self.left = None
        
class BinarySearchTree:
    def __init__(self):
        self.root = None
        
    def insert(self,value):
        new_node = Node(value)
        if self.root is None:
            self.root = new_node
            return True
        temp = self.root
        while(True):
            if new_node.value == temp.value:
                return False
            if new_node.value < temp.value:
                if temp.left is None:
                    temp.left = new_node
                    return True
                temp = temp.left
            else:
                if temp.right is None:
                    temp.right = new_node
                    return True
                temp = temp.right