Binary tree in python

Binary tree vs binary search tree

Binary tree - each node can have at most 2 nodes, Binary Search tree - is a binary tree and put smaller values on the left and larger values on the right of the root.

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)

Binary tree in python

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

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

Source: raw.githubusercontent.com

Binary search tree in python

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

Similar codes

0 vote113 views1 answer
Networkx largest component
Python
0 vote77 views1 answer
Django select_related multiple tables
Python
0 vote120 views1 answer
Arima A date index has been provided, but it has no associated frequency information and so will be ignored when e.g. forecasting
Python
0 vote125 views1 answer
Python dict keys to string
Python
0 vote119 views1 answer
How return the data timestamp after some days in python
Python
0 vote118 views1 answer
Python how to get variable value in dict
Python
80 votes126 views4 answers
Pip for python
Python
0 vote122 views1 answer
How to find number of categories in python
Python
2 votes112 views1 answer
Python how to check which int var is the greatest
Python
1 vote109 views1 answer
Reshape wide to long in pandas
Python