PYTHON

make binary tree in python

"""
Implementation of Binary Tree;
"""

class Node:

    """
    init() : constructor
    """
    def __init__(self,data = None):
        self.data = data
        self.left = None
        self.right = None

    """
    getNode() : get node data;
    """
    def getData(self):
        return self.data

    """
    setData() : set node data;
    """
    def setData(self,data):
        self.data = data


class Tree:

    """
    init() : constructor;
    """    
    def __init__(self):
        self.root = None

    """
    len() : len of the tree;
    """
    def __len__(self):
        return self.height()

    """
    getRoot() : get root node;
    """
    def getRoot(self):
        return self.root

    """
    add() : add nodes;
    """
    def add(self,data):
        if(self.root == None):
            self.root = Node(data)
        else:
            self._add(self.root,data)

    """
    _add() : add method init;
    """
    def _add(self,root,data):
        if(data < root.data):            # Left Sub Tree
            if(root.left is not None):
                self._add(root.left,data)
            else:
                root.left = Node(data)
        else:                           # Right Sub Tree
            if(root.right is not None):
                self._add(root.right,data)
            else:
                root.right = Node(data)

    """
    show() : show tree nodes;
    """    
    def show(self,key=None):       # key: pre,in,post-order;
        if(self.root is not None):
            if(key == "preorder"):
                self.preorder(self.root)
            elif(key == "inorder"):
                self.inorder(self.root)
            elif(key == "postorder"):
                self.postorder(self.root)
            else:
                self._show(self.root)
        else:
            return None

    """
    _show() : show method init;
    """
    def _show(self,root):
        if(root is not None):
            print(root.data,end=", ")          # print;
            self._show(root.left)              # go left;
            self._show(root.right)             # go right;
        return

    """
    preorder() : pre-order tree traversal;
    """
    def preorder(self,root=None):
        if(root is not None):
            print(root.data,end=", ")      # print;
            self.preorder(root.left)       # go left;
            self.preorder(root.right)      # go right;
        return

    """
    inorder() : in-order tree traversal;
    """
    def inorder(self,root=None):
        if(root is not None):
            self.inorder(root.left)            # go left;
            print(root.data,end=", ")          # print;
            self.inorder(root.right)           # go right;
        return 

    """
    postporder() : post-order tree traversal;
    """
    def postorder(self,root=None):
        if(root is not None):
            self.postorder(root.left)
            self.postorder(root.right)
            print(root.data,end=", ")            # print;
        return


    """
    find() : find nodes inside tree;
    """
    def find(self, data):
        if self.root is not None:
            return self._find(self.root,data)
        else:
            return None

    """
    _find() : find method init;
    """
    def _find(self,root,data):
        if(root is not None):
            if data == root.data:
                return f"Node {data}: Found"
            elif (data < root.data):
                return self._find(root.left,data)
            elif (data > root.data):
                return self._find(root.right,data)
        else:
            return f"Node {data}: Not Found"
    
    """
    delete() : delete a not from tree;
    """
    def delete(self,data):
        pass

    """
    height() : height of a tree
    """
    def height(self):
        if(self.root is None):
            return 0
        else:
            return self._height(self.root)

    """
    _height() : height method init;
    """
    def _height(self,root):
        if(root == None):
            return 0
        else:
            lenOne = self._height(root.left)
            lenTwo = self._height(root.right)
            return 1+max(lenOne,lenTwo)
            

python binary tree

class Binarytree:
    def __init__(self, node):
        """

       :param node: root node
       """
        self.node = node
        self.left = None
        self.right = None

    def add_node(self, node):
        """

       :param node: append node
       :return: None
       """
        if node == self.node:
            return

        if node < self.node:
            if self.left:
                self.left.add_node(node)
            else:
                self.left = Binarytree(node)
        else:
            if self.right:
                self.right.add_node(node)
            else:
                self.right = Binarytree(node)

    def search(self, val):
        """

       :param val: value to search in binary tree
       :return: True if found else False
       """
        if val == self.node:
            return True
        if val < self.node:
            if self.left:
                return self.left.search(val)
            else:
                return False
        else:
            if self.right:
                return self.right.search(val)
            else:
                return False

    def print_nodes(self):
        """
        print all node values to console window
       :return: None
       """

        if self.left:
            self.left.print_nodes()

        print(self.node)

        if self.right:
            self.right.print_nodes()

        return False


def build_tree(node):
    """

   :param node: list of nodes
   :return: Binarytree with nodes
   """
    root = Binarytree(node[0])
    for i in range(1, len(node)):
        root.add_node(node[i])
    return root


if __name__ == '__main__':
    nodes = [30, 10, 40, 22, 15, 18]
    tree = build_tree(nodes)
    tree.add_node(18)
    tree.add_node(20)
    print("15 found in binary tree", tree.search(15))
    print("100 found in binary tree", tree.search(100))
    tree.print_nodes()

binary tree in python

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

Binary Tree 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())

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.
'''
# 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)

binary search tree in python

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

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)