DATA Structures :Binary Search Trees


Bnary Search Trees

Binary tree is a tree that each node in it has maximum of two children. Binary search tree (BST) is a binary tree which its elements positioned in special order. In each BST all values(i.e key) in left sub tree are less than values in right sub tree.

This is a simple implementation of Binary Search Tree Insertion using Python.

this slowpoke moves

class Node:
 def __init__(self, val):
 self.l_child = None
 self.r_child = None
 self.data = val


def insert(root, node):
     if root is None:
         root = node
     else:
         if  root.data > node.data:
             if root.l_child is None:
                 root.l_child = node
             else:
                 insert(root.l_child, node)
     else:
         if root.r_child is None:
             root.r_child = node
         else:
             insert(root.r_child, node)

Traversing to all nodes in BST trees
 
we have different traversal techniques as listed below:

1) In order: 
In this traversal technique, we traverse the left subtree first till there are no more nodes in the left subtree. After this, we visit the root node and then proceed to traverse the right subtree until there are no more nodes to traverse in the right subtree. Thus the order of inOrder traversal is left->root->right.


def in_order_print(root):
     if not root:
         return
     in_order_print(root.l_child)
     print root.data
     in_order_print(root.r_child)



2) Pre-order: 
For preorder traversal technique, we process the root node first, then we traverse the entire left subtree and finally, we traverse the right subtree. Hence the order of preorder traversal is root->left->right.

def pre_order_print(root):
     if not root:
         return
     print root.data
     pre_order_print(root.l_child)
     pre_order_print(root.r_child) 


3) Post-order: In the post-order traversal technique, we traverse the left subtree, then the right subtree and finally the root node. The order of traversal for the postorder technique is left->right->root.

def post_order_print(root):
     if not root:
         return
     post_order_print(root.l_child)
     post_order_print(root.r_child)
     print root.data



Binary Search Tree - Deletion

Before starting with deletion I just want to put some lights on what is a Binary search tree(BST), Each node in a BST can have maximum of two nodes(left and right child).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. Deleting a node in a tree while maintaining its Binary search tree property. 


There are three cases to be considered while deleting a node. 
Case 1: Node to be deleted is the leaf node. 
Case 2: Node to be deleted has one child.
Case 3: Node to be deleted has both children.

Implementation in c++

struct node
    {
          int data;
         node *left, *right;
    };
node* delete_node(node *root, int data)
{
     if(root == nullptr) return root;
     else if(data < root->data) root->left = delete_node(root->left, data);
     else if(data > root->data) root->right = delete_node(root->right, data);
     else
     {
         if(root->left == nullptr && root->right == nullptr) // Case 1
             {
                 free(root);
                 root = nullptr;
             }
         else if(root->left == nullptr) // Case 2
             {
                 node* temp = root;
                 root= root->right;
                 free(temp);
              }
          else if(root->right == nullptr) // Case 2
             {
                 node* temp = root;
                  root = root->left;
                   free(temp);
             }
     else // Case 3
     {
         node* temp = root->right;
         while(temp->left != nullptr) temp = temp->left;
         root->data = temp->data;
         root->right = delete_node(root->right, temp->data);
     }
 }
     return root;
}

Time complexity of above code is O(h), where h is the height of the tree.




 If Any one need our help regarding any subject are technology we can help you. Please Subscribe and Comment

Contact Persons

Jane

Rajesh G

Software Developer At GGK

gundupallirajesh@gmail.com

Mukthapuram

Haswanth M

Front End Developer at TCS

haswanthmuktha@gmail.com

John

Poorna K

FullStack Dev at Wipro

poorna.k26@gmail.com

Comments

Post a Comment

Popular posts from this blog

JavaScript: Async functions (async/await)

Image
JavaScript: Async functions (async/await) I am sure that many of you are using async and await already. But, I think it deserves a little more attention.   Every one should remember Mozilla docs is your friend. Here is the MDN definition for async and await: async: “An asynchronous function is a function which operates asynchronously via the event loop, using an implicit Promise to return its result. But the syntax and structure of your code using async functions is much more like using standard synchronous functions.”   await:  “An async function can contain an await expression that pauses the execution of the async function and waits for the passed Promise's resolution, and then resumes the async function's execution and returns the resolved value. Remember, the await keyword is only valid inside async functions.”   Confused………..   Lets put this defina...
Read more

Angular 2+ :@view Child

Image
ANGULAR2 @view Child Viewchild offers one way interaction fro . m parent to child. There is no return mes . sage or output from child when ViewChild is used. ViewChild is used for component to template communication. It is used to ref . erence a directive or element or component.  Example  let element = document.getElementById('elementId'); @ViewChild('elementV . ariable') elementRef; // template reference variable @ViewChild(NgModel) filterInput: NgModel; // a ngular directive - on template would look like: <input [(ngModel)]='listfilter'> @ViewChild(Pare . ntComponent) Parent: (ParentComponent) // child com . ponent - on template would look like: <child-component[input1]='some.input'> Detailed Example We ha . ve a DataListC . omponent that shows som . e information. DataListComponent has PagerComponent as it's child. When user . makes a search on DataListComponent, it gets a data from a servic . e and ask Pag...
Read more

Angular -Lazy Loading

Lazy Loading   What Is Lazy Loading..? Lazy loading is a process were angular loads the modules only when it is needed without loading all at once. It is also called as on-demand loading.   Why Lazy Loading..?   Lazy loading modules helps us decrease the start-up time. Angular app can become bigger in size if we add more and more modules for improving features of the app. As the app grows bigger the slower it loads.   By Loading only a part of the app (i.e. lazy loading), the app appears to run faster to the user. The faster loading app gives you a performance boost and results in good user experience.   Lazy loading reduce the bundle size of the app which help to boot fast.   How Lazy loading Work…? In angular lazy loading works on module level. Single Components cannot be loaded lazily. Angular Router Module is the place where we implement lazy Loading. The loadChildren method of the Angular Router is responsible to load the ...
Read more

DBMS-Data Models

Image
Data Models   A data model is a picture or description which shows how the data is to be arranged to achieve a given task. It is a clear model which specifies how the data items are arranged in a given model. Some data models which gives a clear picture which shows the manner in which the data records are connected or related within a file structure. These are called structural data models. DBMS organize and structure data so that it can be retrieved and manipulated by different users and application programs The data structures and access techniques provided by a particular DBMS are called its data model.     Types Of Data Models:   1)Hierarchical databases model 2)Network databases model 3)Relational databases model 4) Object oriented databases model   Hierarchical databases model:   Hierarchical Databases is most commonly used with mainframe systems. It is one of the oldest methods of organizing and storing data and ...
Read more

OOPS Concepts-JAVA

Image
Java OOPs (Object-Oriented Programming) Concepts(oo) Note: This blog is just to share our Knowledge if there are any mistakes please let us know. What is oo programming..? OO has strong historical roots in other paradigms and practices. It came about to address problems commonly grouped together as the “software crisis.” It does not solve any questions its just a piece of solution for problems.   Object Oriented programming gives solution to a problem by using these concepts. OOPs Concept in Java ·         Polymorphism ·         Inheritance ·         Encapsulation ·         Abstraction ·         Class ·         Object ·         Method ·         Message Passing   Note: We are...
Read more