🌵
Christian's Wiki
/
📖
Data Structures & Algorithms
/
Algorithm
/
Binary Search Tree

Binary Search Tree

‣
Data Structure: What is a Binary Search Tree? What are the operations it supports and give their runtimes. Implement it

A Binary Search Tree is a node based binary tree data structure

Properties

  • The left subtree of a node contains only nodes with keys lesser than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be binary search trees.
  • There must be no duplicate nodes.

At minimum it should support, insert, search, (optional: minimum), delete operations.

Related Problems:

  • Construct BST from given preorder traversal
  • Construct BST from given postorder traversal
‣
What operations should a of Binary Search Tree support?

insert() minimum() delete() search()

‣
What are their runtimes?

Insert: O(h)O(h)O(h) where h is the height of the BST

Search: O(h)O(h)O(h) where h is the height of the BST (average case), O(n)O(n)O(n) worst case.

Delete: O(n)O(n)O(n) 

class Node(object):
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        ''' 
				For inserting the data in the Tree 
				'''
        if self.data == data:
            return False        # no duplicates
				elif data < self.data:
            ''' 
								Data less than the root data is 
								placed to the left of the root 
						'''
            if self.left:
                return self.left.insert(data)
            else:
                self.left = Node(data)
                return True

        else:
            ''' 
								Data greater than the root data is 
								placed to the right of the root 
						'''
            if self.right:
                return self.right.insert(data)
            else:
                self.right = Node(data)
                return True

    def minimum(self, node):
        current = node

        # loop down to search the leftmost leaf
				while(current.left is not None):
            current = current.left

        return current

    def delete(self, data):
        ''' For deleting the node '''
        if self is None:
            return None

        '''
						if current node's data is less than that of
						root node, then only search in left 
						subtree else right subtree
				'''
				if data < self.data:
            self.left = self.left.delete(data)
        elif data > self.data:
            self.right = self.right.delete(data)
        else:
            # deleting node with one child
						if self.left is None:
                temp = self.right
                self = None
                return temp
            elif self.right is None:
                temp = self.left
                self = None
                return temp

            # deleting node with two children
						# first get the inorder successor
            temp = self.minimum(self.right)
            self.data = temp.data
            self.right = self.right.delete(temp.data)

        return self

    def search(self, data):
        ''' 
						This function checks whether the 
						specified data is in tree or not 
				'''
        if(data == self.data):
            return True
        elif(data < self.data):
            if self.left:
                return self.left.search(data)
            else:
                return False
        else:
            if self.right:
                return self.right.search(data)
            else:
                return False

class Tree(object):
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root:
            return self.root.insert(data)
        else:
            self.root = Node(data)
            return True

    def delete(self, data):
        if self.root is not None:
            return self.root.delete(data)

    def search(self, data):
        if self.root:
            return self.root.search(data)
        else:
            return False