How to create a Binary Tree Program ( Python / C / C++ )

What is a binary tree?
A binary tree is categorized as an abstract data type, whose (I/O) ,(R/W) operations are handled by the user defined functions.A binary tree is a special case of a tree DS where each node except leaf nodes has two children's .

for creating a binary tree we will define a class / structure node which will contain the members(left child and right child) and the value.

class node:
    def __init__(self, value=None):
        self.value = value
        self.left_child = None
        self.right_child = None

Now , we will write the code for inserting elements in our binary tree, we will create the function in another class containing a member which will store the address of root node and add all successive elements under the root node .

def insert(self, value):
    if self.root == None:
        self.root = node(value)
    else:
        self._insert(value, self.root)

def _insert(self, value, cur_node):
    if value < cur_node.value:
        if cur_node.left_child == None:
            cur_node.left_child = node(value)
        else:
            self._insert(value, cur_node.left_child)
    elif value > cur_node.value:
        if cur_node.right_child == None:
            cur_node.right_child = node(value)
        else:
            self._insert(value, cur_node.right_child)

    else:
        print("already exists")

for inserting an element we are using two functions one is recursive and other one for checking if the binary tree is empty or not and if not then it calls the recursive function for traversing the tree and insert the node (element) in the right place.

def print_tree(self):
    if self.root != None:
        self._print_tree(self.root)

def _print_tree(self, cur_node):
    if cur_node != None:
        self._print_tree(cur_node.left_child)
        print(cur_node.value)
        self._print_tree(cur_node.right_child)

this is similar to the insert function : the recursive function ( _print_tree() ) traverses /prints the values  :

from left -> right ( left nodes->right nodes->root node ->left nodes ->right nodes)
from bottom to top

The output will be: 8,7,9,10,18,19,15

Source Code:

Choose a language:

  

C/C++

//bst
 include<stdio.h>
 include<stdlib.h>
 typedef struct node{
     int val;
     struct node* lchild;
     struct node* rchild;
 }* node;
 node create(int val){
     node nt=(node)malloc(sizeof(struct node));
     if(!nt){
         printf("Memory allocation error\n");
         exit(0);
     }
     nt->val=val;
     nt->lchild=nt->rchild;
     return nt;
 }
 void _insert(node root,node nt){
     if(root->val>nt->val)
         if(root->lchild==NULL)
             root->lchild=nt;
         else
             _insert(root->lchild,nt);
     else if(root->valval)
         if(root->rchild==NULL)
             root->rchild=nt;
         else
             _insert(root->rchild,nt);
     else
         printf("Node already exists\n");
 }
 void insert(node* root,int val){
     node nt=create(val);
     if(*root==NULL)
         *root=nt;
     else
         _insert(*root,nt);
 }
 void _preorder(node root){
     if(root){
     printf("%d ",root->val);
     _preorder(root->lchild);
     _preorder(root->rchild);
     }
 }
 void preorder(node root){
     if(!root){
         printf("Empty BST\n");
         return;
     }
     _preorder(root);
 }
 void _postorder(node root){
     if(root){
     _postorder(root->lchild);
     _postorder(root->rchild);
     printf("%d ",root->val);
     }
 }
 void postorder(node root){
     if(!root){
         printf("Empty BST\n");
         return;
     }
     _postorder(root);
 }
 void _inorder(node root){
     if(root){
     _inorder(root->lchild);
     printf("%d ",root->val);
     _inorder(root->rchild); }
 }
 void inorder(node root){
     if(!root){
         printf("Empty BST\n");
         return;
     }
     _inorder(root);
 }
 int _search_bst(node root,int val,int l){
     if(root==NULL)return;
     if(root->val==val)
         return l;
     else if(root->val>val)
         if(root->lchild==NULL)
             return -1;
         else
             _search_bst(root->lchild,val,l+1);
     else 
         if(root->rchild==NULL)
             return -1;
         else
             _search_bst(root->rchild,val,l+1);
 }
 int search_bst(node root,int val){
     if(root==NULL){
         printf("Empty BST\n");
         return -1;
     }
     return _search_bst(root,val,0);
 }
 void create_bst(node* root){
     int c,n;
     printf("Enter number of values you want to insert\n");
     scanf("%d",&n);
     printf("Enter values\n");
     while(n--){
         //printf("Enter value \n");
         scanf("%d",&c);
         insert(root,c);
         //printf("enter 0 to stop insertion\n");
         //scanf("%d",&c);
     }
 }
 void main(){
     node root=NULL;
     int ch;
     while(1){
     printf("\nEnter your choice\n");
     printf("0)insert_multiple\n1)insert\n2)preorder\n3)inorder\n4)postorder\n5)search\n6)exit\n");
     scanf("%d",&ch);
 switch(ch){     
     case 0:create_bst(&root);         break;
     case 1:printf("Enter value\n");     
             scanf("%d",&ch);                             
            insert(&root,ch);         break;
     case 2:preorder(root);break;
     case 3:inorder(root);break;
     case 4:postorder(root);break;
     case 5:printf("Enter value to be searched\n");          
             scanf("%d",&ch);
            ch=search_bst(root,ch)+1;
         if(ch) 
              printf("node exists at level=%d\n",ch-1);
         else             printf("not found\n");
         break;
     case 6:exit(0); } }
 }




Python

 # https://www.qxcoding.com/ 

class node:
    def __init__(self, value=None):
        self.value = value
        self.left_child = None
        self.right_child = None


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

    def insert(self, value):
        if self.root == None:
            self.root = node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, cur_node):
        if value < cur_node.value:
            if cur_node.left_child == None:
                cur_node.left_child = node(value)
            else:
                self._insert(value, cur_node.left_child)
        elif value > cur_node.value:
            if cur_node.right_child == None:
                cur_node.right_child = node(value)
            else:
                self._insert(value, cur_node.right_child)

        else:
            print("already exists")

    def print_tree(self):
        if self.root != None:
            self._print_tree(self.root)

    def _print_tree(self, cur_node):
        if cur_node != None:
            self._print_tree(cur_node.left_child)
            print(cur_node.value)
            self._print_tree(cur_node.right_child)

    def height(self):
        if self.root == None:
            return 0
        else:
            return self._height(self.root, 0)

    def _height(self, cur_node, cur_height):
        if cur_node == None: return cur_height
        left_height = self._height(cur_node.left_child, cur_height + 1)
        right_height = self._height(cur_node.right_child, cur_height + 1)
        return max(left_height, right_height)

    def delete_tree(self):
        self.root = None
        # freeing the memory will be taken care by garbage collector


if __name__ == '__main__':
    b1 = BinaryTree()
    b1.insert(5)
    b1.insert(10)
    b1.insert(6)
    b1.insert(8)
    b1.insert(3)
    b1.insert(4)
    b1.insert(2)
    b1.print_tree()
    b1.delete_tree()

if any doubts or queries please comment