A Binary Search Tree (BST) is a tree in which all the nodes follow mentioned properties :
- The left sub-tree of a node has a key less than or equal to its parent node’s key.
- The right sub-tree of a node has a key greater than to its parent node’s key.

Lets create or insert these nodes using programming:
Creation or Insertion of BST with Python:
Step-1: Create Node Class : Intially Node left and right child are none and constructor take node value as an argument.
class Node: # Define the Constructor def __init__(self,key): self.left = None self.right = None self.val = key
Step-2: Create BST Class : It contains insert_bst method, take two arguments-root and node, that is the object of Node class defined in Step1.
root.val,node.val,root.left,root.right are the Node object fields defined in Step1.
class BST: #Insert the Node object(defined in Step 1) into tree def insert_bst(self,root,node): if root is None: root = node else: if root.val < node.val: if root.right is None: root.right = node else: self.insert_bst(root.right, node) else: if root.left is None: root.left = node else: self.insert_bst(root.left, node)
Step-3: How do we know that Binary search tree formed or not? Lets print the node values using Inorder Tree Traversal method. It consist inorder_bst method that take the Node class object defined in Step-1 as an argument.
def inorder_bst(self,root): if root: self.inorder_bst(root.left) print(root.val) self.inorder_bst(root.right)
Lets combine Step-1,Step 2 and Step-3 steps and run it.
class Node: # Define the Constructor def __init__(self,key): self.left = None self.right = None self.val = key class BST: #Insert the Node object(defined in Step 1) into tree. def insert_bst(self,root,node): if root is None: root = node else: if root.val < node.val: if root.right is None: root.right = node else: self.insert_bst(root.right, node) else: if root.left is None: root.left = node else: self.insert_bst(root.left, node) #print the node using Inorder Traversal def inorder_bst(self,root): if root: self.inorder_bst(root.left) print(root.val) self.inorder_bst(root.right)
#Create the object of Node class
rtn = Node(100)
#Create the object of BST class
obj_bst=BST()
obj_bst.insert_bst(rtn,Node(80))
obj_bst.insert_bst(rtn,Node(70))
obj_bst.insert_bst(rtn,Node(90))
obj_bst.insert_bst(rtn,Node(110))
obj_bst.insert_bst(rtn,Node(120))
obj_bst.insert_bst(rtn,Node(105))
obj_bst.inorder_bst(rtn)
Output:

Inorder traversal of BST always produces sorted output.
The worst case time complexity of search and insert operations is O(h) where h is height of Binary Search Tree.
Hopefully you understand the creation of BST. Please do comment in case of any questions and share it further if you liked it.
Happy Learning 🙂
0 Comments