Binary Search Tress - Insertion & Deletion

Binary Search Tree is a node-based binary tree data structure which has the following properties:

·       The left subtree of a node contains only nodes with keys lesser than the node’s key.

·       The right subtree of a node contains only nodes with keys greater than the node’s key.

·    The left and right subtree each must also be a binary search tree.

Basic Operations: Following are the basic operations of a tree 

Search − Searches an element in a tree.

Insert − Inserts an element in a tree.

Pre-order Traversal − Traverses a tree in a pre-order manner.

In-order Traversal − Traverses a tree in an in-order manner.

Post-order Traversal − Traverses a tree in a post-order manner.

Binary Search Tree (Search and Insertion)

Binary Search Tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes.

Search Operation

        Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

Insert Operation

      Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

• Binary Search Tress - Insertion

Binary Search Tress -  Deletion :Deletion of a node is performed as follows,

Deleting node has no child, therefore just delete the node(made to point NULL)

Deleting node has 1 child, swap the key with the child and delete the child.

Deleting node has 2 children, in this case swap the key with inorder successor of the deleting node. It should be noted, inorder successor will be the minimum key in the right subtree (of the deleting node).