Python

"""Binary Search Tree

Included:
	- Insert
    - Find data/ minimum/ maximum
    - Size
    - Height
    - Traversals (Inorder, preorder, postorder)
    - Test Code for it
    
Not included:
	- Delete
    - Display (as 2D BST)
	and others...
"""

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

    # Insert a node
    def put(self, data):
        if self.root is None: # BST empty
            self.root = Node(data)
        else:
            curr = self.root # initialise curr pointer
            while curr:
                if data < curr.data: # data put at left
                    if curr.left:
                        curr = curr.left
                    else: # no left child
                        curr.left = Node(data)
                        break
                else: # data put at right
                    if curr.right:
                        curr = curr.right
                    else:  # no right child
                        curr.right = Node(data)
                        break   
                        
    def find(self, data):
        curr = self.root   # start from root
        while curr:
            if data < curr.data:  # data at left
                curr = curr.left
            elif data > curr.data:    # data at right
                curr = curr.right
            else:
                return True # found
        return False
    
    def min_of(self):
        curr = self.root # start from root
        while curr.left:
            curr = curr.left # keep going left
        return curr.data
        
    def max_of(self):
        curr = self.root # start from root
        while curr.right:
            curr = curr.right # keep going right
        return curr.data
    
    def size(self):
        def go(node): # helper
            if node:
                return 1 + go(node.left) + go(node.right)
            return 0
        return go(self.root)   
    
    def height(self):
        def go(node): # helper
            if node:
                return 1 + max(go(node.left), go(node.right))
            return -1 # it has -1 if empty
        return go(self.root)

        
    # In_order
    def in_order(self):
        lst = [] # results
        def go(node): # helper
            nonlocal lst
            if node: # If node exists
                go(node.left) # left
                lst.append(node.data) # Node
                go(node.right) # Right
        go(self.root)
        return lst
    
    # Pre_order
    def pre_order(self):
        lst = [] # results
        def go(node): # helper
            nonlocal lst
            if node: # If node exists
                lst.append(node.data) # Node
                go(node.left) # left
                go(node.right) # Right
        go(self.root)
        return lst
    
    # Post_order
    def post_order(self):
        lst = [] # results
        def go(node): # helper
            nonlocal lst
            if node: # If node exists
                go(node.left) # left
                go(node.right) # Right
                lst.append(node.data) # Node
        go(self.root)
        return lst

# Test
from random import randint, sample
def BST_tester(BST):
    r = randint(5, 10)
    lst = [randint(10, 100) for _ in range(r)]
    print(f"List: {lst}", 
          f"Sorted: {sorted(lst)}",
          sep = "
", end = "

")
    
    B = BST()
    for item in lst:
        B.put(item)
    lst.sort()
    print("AFTER INSERTION:",
          f"Size: {B.size()} | {B.size() == len(lst)}",
          f"Height: {B.height()} | I can't code the display for this",
          f"Min: {B.min_()} | {B.min_() == min(lst)}",
          f"Max: {B.max_()} | {B.max_() == max(lst)}",
          sep = "
", end = "

")
    
    items = sample(lst, 5) + [randint(10, 100) for _ in range(5)] # 5 confirm in list, 5 might be in list
    found = [B.find(_) for _ in items]
    zipped = list(zip(items, found))
    inlst, notinlst = zipped[:5], zipped[5:] 
    print(f"Sampled from lst: {inlst} | All True: {all(found[:5])}",
          f"Random: {notinlst}",
          sep = "
", end = "

")
    
    print(f"Inord: {B.in_ord()} | Correct Insertion: {lst == B.in_ord()}",
          f"Preord: {B.pre_ord()}",
          f"Postord: {B.post_ord()}",
          sep = "
")
BST_tester(BST)

Binary Search tree implementation in python

"""
	              17
		    /    
		   /      
		  /	   		  
		 4         20
		/	   /	
	       /         /  
	      /         /    
	     1      9   18    23
			        
				 
				   
				   34
							 
"""							 

# Binary Search Tree implementation in Python

class BinaryTreeNode():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
    def add_child(self, data):
        if data == self.data: # check if the of new data exist already in the tree, if yes don't add
            return
        
        if data < self.data:
            # Add to left subtree
            if self.left:
                self.left.add_child(data) # Recursively call the add_child method to add the data to an appropriate place
            else:
                self.left = BinaryTreeNode(data)
        else:
            # Add to right subtree
            if self.right:
                self.right.add_child(data) # Recursively call the add_child method to add the data to an appropriate place
            else:
                self.right = BinaryTreeNode(data)
    
    # Visit Left subtree, then Root node and finaly Right subtree
    def in_order_traversal(self):  # Left - Root - Right
        elements = []
        
        # Getting all elements of the Left Subtree    
        if self.left:
            elements += self.left.in_order_traversal() # Recursively get all the elements of the left subtree and add them into the list
        elements.append(self.data) # Adding the root node to the list
        
        # Getting all elements of the Right Subtree    
        if self.right:
            elements += self.right.in_order_traversal() # Recursively get all the elements of the right subtree and add them into the list
        return elements
        
    # Get all elements from the Root node then the left subtree and finanally the Right subtree 
    def pre_order_traversal(self): # Root - Left - Right
        elements = []
        
        elements.append(self.data)
        
        if self.left:
            elements += self.left.pre_order_traversal()  # Recursively get all the elements of the left subtree and add them into the list
        
        if self.right:
            elements += self.right.pre_order_traversal()  # Recursively get all the elements of the right subtree and add them into the list

        
        return elements # get the Root node element
        
    # Get all elements from the Right subtree then the left subtree and finally the Root node    
    def post_order_traversal(self):
        elements = []
        
        if self.left:
            elements += self.left.post_order_traversal()  # Recursively get all the elements of the left subtree and add them into the list
        
        if self.right:
            elements += self.right.post_order_traversal()  # Recursively get all the elements of the right subtree and add them into the list
            
        elements.append(self.data) # Get the Root node element
        
        return elements
        
        
    def search_element(self, elem): # complexity of log n O(log n)
        if self.data == elem:
            return True
        elif elem < self.data:
            # This means if present, element would be on the left 
            if self.left:
               return self.left.search_element(elem)  
            else:
                return False
            
        else:
            # This means if present, element would be on the right
            if self.right:
                return self.right.search_element(elem)  
            else:
                return False
    
    
    def sum_of_all_elements_in_tree(self):
        return sum(self.in_order_traversal())
        
    def max_element_in_tree(self):
        return max(self.in_order_traversal())    
    
    def min_element_in_tree(self):
        return min(self.in_order_traversal())    
    
    
# Tree Builder helper method
def build_binary_tree(lst_elem: list):
    if len(lst_elem) >1:
        root_node = BinaryTreeNode(lst_elem[0])
        for i in lst_elem[1:]:
            root_node.add_child(i)
       
        #root_node.search_element(20)
        #print(root_node.in_order_traversal())
        return root_node
    else:
        return print("Insufficient number of elements")
        

if __name__ == '__main__':
   mt = build_binary_tree([17, -5, 4, 1, 20, 9, -1, 23, 18, 0, 34])
   print("In Order Traversal", mt.in_order_traversal())
   print("Post Order Traversal", mt.post_order_traversal())
   print("Pre Order Traversal", mt.pre_order_traversal())
   print(mt.search_element(20))
   print("Sum of all elemnts in tree", mt.sum_of_all_elements_in_tree())
   print("Max element in tree is", mt.max_element_in_tree())
   print("Min element in tree is", mt.min_element_in_tree())

Python code for binary search tree

# বাইনারি সার্চ ট্রি-এর ক্ষেত্রে ২ টি বিষয় মাথায় রাখতে হবে:
'''
১. যদি ট্রি-তে আগে থেকে কোনো নোড না থাকে (অর্থাৎ বর্তমান root নোড none থাকবে),
            তাহলে নতুন যোগ করা নোডটিই হবে ট্রি- এর root নোড । আবার-
২. নতুন নোডটি যদি root নোডের সরাসরি চাইল্ড হয়, তাহলেও root  নোডের  পরিবর্তন ঘটবে।
            এ কারণেই আমরা root নোডকে রিটার্ন করি।
'''
# There are two things to keep in mind when it comes to binary search trees:
'''
1. If the tree does not already have a node (ie the existing root node will have none), 
                then the newly added node will be the root node of the tree. Again
2. If the new node is a direct child of the root node, the root node will also change. 
                This is why we return to the root node.
'''
# 1st system:

class TreeNode:
    def __init__(self,data):
        self.data = data
        self.parent = None
        self.left = None
        self.right = None

    def __repr__(self):
        return repr(self.data)

    def add_left(self, node):
        self.left = node
        if node is not None:
            node.parent = self

    def add_right(self, node):
        self.right = node
        node.parent = self

# now bst_insert:
def bst_insert(root,node):
    last_node = None
    current_node = root
    while current_node is not None:
        last_node = current_node
        if node.data < current_node.data:
            current_node = current_node.left
        else:
            current_node = current_node.right
    if last_node is None:
        # tree was empty. node is the only node, hence root
        root = node # new node add
    elif node.data < last_node.data:
        last_node.add_left(node)
    else:
        last_node.add_right(node)
    return root
'''
              _10_
             /    
            5      17
           /      /  
          3      12  19
         /              
        1   4         
   
'''
# now create_bst:
def create_bst():
    li = list(map(int,input().split()))
    root = TreeNode(li)
    for item in root:
        node = TreeNode(item)
        root = bst_insert(root, node)
    return root

# In_order tree traverse:
def in_order(node):
    if node.left:
        in_order(node.left)
    print(node)
    if node.right:
        in_order(node.right)

# bst- tree minimum node:
def bst_minimum(root):
    while root.left is not None:
        root = root.left
    print(root)

# bst_tree maximum node:
def bst_maximum(root):
    while root.right is not None:
        root = root.right
    print(root)


# এখন আমরা BST-তে কোনো ডেটা খুঁজে বের করার ফাংশন টি লিখে ফেলি।
# Now we write the function to find any data in BST.
def best_search(node,key):
    while node is not None:
        if node.data == key:
            return node
        if key < node.data:
            node = node.left
        else:
            node = node.right
    return node

# Now check to your code:
if __name__ == "__main__":
    root = create_bst()
    print("Tree is root =",root)
    print()
    # In_order tree traverse:
    print("In_order Tree:")
    in_order(root)
    print()

    # bst- tree minimum node:
    print("Minimum node:")
    bst_minimum(root)
    print()

    # bst_tree maximum node:
    print("Maximum node:")
    bst_maximum(root)
    print()

    # input with searching:
    print("bst_search:")
    for key in [int(input("Please Enter the search key: ")),int(input("Please Enter the search key: "))]:
        print("Searching =",key)
        result = best_search(root, key)
        print("Result =",result)

python binary tree search

def search(node, search_item):

    # Base case for recursion:
    # The recursion will stop if the search item has been found
    if search_item == node.data:
        return True

    # Check if the search item is greater than the node data
    # and there is another node to the right to check
    elif search_item > node.data and node.right is not None:
        return search(node.right, search_item)

    # Check if the search item is less than the node data
    # and there is another node to the left to check
    elif search_item < node.data and node.left is not None:
        return search(node.left, search_item)

    # Otherwise the search item does not exist
    else:
        return False

binary search tree in python

Binary Search Tree at this link:
  
https://github.com/shreyasvedpathak/Data-Structure-Python/tree/master/BinaryTrees

implementation of binary search tree in python

# Python program to demonstrate
# insert operation in binary search tree
 
# A utility class that represents
# an individual node in a BST
 
 
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
 
# A utility function to insert
# a new node with the given key
 
 
def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val == key:
            return root
        elif root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root
 
# A utility function to do inorder tree traversal
 
 
def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)
 
 
# Driver program to test the above functions
# Let us create the following BST
#    50
#  /     
# 30     70
#  /  / 
# 20 40 60 80
 
r = Node(50)
r = insert(r, 30)
r = insert(r, 20)
r = insert(r, 40)
r = insert(r, 70)
r = insert(r, 60)
r = insert(r, 80)
 
# Print inoder traversal of the BST
inorder(r)

Binary search tree in python

# বাইনারি সার্চ ট্রি-এর ক্ষেত্রে ২ টি বিষয় মাথায় রাখতে হবে:
'''
১. যদি ট্রি-তে আগে থেকে কোনো নোড না থাকে (অর্থাৎ বর্তমান root নোড none থাকবে),
            তাহলে নতুন যোগ করা নোডটিই হবে ট্রি- এর root নোড । আবার-
২. নতুন নোডটি যদি root নোডের সরাসরি চাইল্ড হয়, তাহলেও root  নোডের  পরিবর্তন ঘটবে।
            এ কারণেই আমরা root নোডকে রিটার্ন করি।
'''
# There are two things to keep in mind when it comes to binary search trees:
'''
1. If the tree does not already have a node (ie the existing root node will have none), 
                then the newly added node will be the root node of the tree. Again
2. If the new node is a direct child of the root node, the root node will also change. 
                This is why we return to the root node.
'''

# second system:

class TreeNode:
    def __init__(self,data):
        self.data = data
        self.parent = None
        self.left = None
        self.right = None

    def __repr__(self):
        return repr(self.data)

    def add_left(self, node):
        self.left = node
        if node is not None:
            node.parent = self

    def add_right(self, node):
        self.right = node
        node.parent = self

# now bst_insert:
def bst_insert(root,node):
    last_node = None
    current_node = root
    while current_node is not None:
        last_node = current_node
        if node.data < current_node.data:
            current_node = current_node.left
        else:
            current_node = current_node.right
    if last_node is None:
        # tree was empty. node is the only node, hence root
        root = node # new node add
    elif node.data < last_node.data:
        last_node.add_left(node)
    else:
        last_node.add_right(node)
    return root
'''
              _10_
             /    
            5      17
           /      /  
          3      12  19
         /              
        1   4         
   
'''
# now create_bst:
def create_bst():
    root = TreeNode(10)
    for item in [5,17,3,7,12,19,1,4]:
        node = TreeNode(item)
        root = bst_insert(root, node)
    return root

# In_order tree traverse:
def in_order(node):
    if node.left:
        in_order(node.left)
    print(node)
    if node.right:
        in_order(node.right)

# bst- tree minimum node:
def bst_minimum(root):
    while root.left is not None:
        root = root.left
    print(root)

# Node transfer:
def bst_transfer(root, current_node, new_node):
    if current_node.parent is None:
        root = new_node
    elif current_node == current_node.parent.left:
        current_node.parent.add_left(new_node)
    else:
        current_node.parent.add_right(new_node)
    return root

# Node delete:
def bst_delete(root,node):
    if node.left is None:
        root = bst_transfer(root,node,node.right)
    elif node.right is None:
        root = bst_transfer(root,node,node.left)

    else:
        min_node = bst_minimum(node.right)
        if min_node.parent != node:
            root = bst_transfer(root,min_node,min_node.right)
            min_node.add_right(node.right)
        root = bst_transfer(root,node,min_node)
        min_node.add_left(node.left)
    return root



# এখন আমরা BST-তে কোনো ডেটা খুঁজে বের করার ফাংশন টি লিখে ফেলি।
# Now we write the function to find any data in BST.
def best_search(node,key):
    while node is not None:
        if node.data == key:
            return node
        if key < node.data:
            node = node.left
        else:
            node = node.right
    return node

# Now check to your code:
if __name__ == "__main__":
    root = create_bst()
    print("Tree is root =",root)
    print()

    print("BST:")
    in_order(root)

    for key in [1,5,10]:
        node = best_search(root,key)
        print("will delete =", node)
        root = bst_delete(root,node)
        print("BST:")
        in_order(root)

Search

code to printing a binary search tree in python

Binary Search Tree python

Binary Search tree implementation in python

Python code for binary search tree

python binary tree search

binary search tree in python

implementation of binary search tree in python

Binary search tree in python

ADD CONTENT