A Binary Search Tree (BST) is a binary tree where each node stores a key or value)

A Binary Search Tree (BST) is a binary tree where each node stores a key or value)

• 1.
  Presented By, M.Sangeetha, AP/IT,
• 3.
  A full binarytree is a tree in which every node other than the leaves has two children. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
• 8.
  Search Insertion Deletion
• 9.
   Step 1- Read the search element from the user.  Step 2 - Compare the search element with the value of root node in the tree.  Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function  Step 4 - If both are not matched, then check whether search element is smaller or larger than that node value.  Step 5 - If search element is smaller, then continue the search process in left subtree.  Step 6- If search element is larger, then continue the search process in right subtree.  Step 7 - Repeat the same until we find the exact element or until the search element is compared with the leaf node  Step 8 - If we reach to the node having the value equal to the search value then display "Element is found" and terminate the function.  Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then display "Element is not found" and terminate the function.
• 10.
   Step 1- Create a newNode with given value and set its left and right to NULL.  Step 2 - Check whether tree is Empty.  Step 3 - If the tree is Empty, then set root to newNode.  Step 4 - If the tree is Not Empty, then check whether the value of newNode is smaller or larger than the node (here it is root node).  Step 5 - If newNode is smaller than or equal to the node then move to its left child. If newNode is larger than the node then move to its right child.  Step 6- Repeat the above steps until we reach to the leaf node (i.e., reaches to NULL).  Step 7 - After reaching the leaf node, insert the newNode as left child if the newNode is smaller or equal to that leaf node or else insert it as right child.
• 11.
  Case 1: Deletinga Leaf node (A node with no children) Case 2: Deleting a node with one child Case 3: Deleting a node with two children
• 12.
  Step 1 -Find the node to be deleted using search operation Step 2 - Delete the node using free function (If it is a leaf) and terminate the function.
• 13.
  Step 1 -Find the node to be deleted using search operation Step 2 - If it has only one child then create a link between its parent node and child node. Step 3 - Delete the node using free function and terminate the function.
• 14.
   Step 1- Find the node to be deleted using search operation  Step 2 - If it has two children, then find the largest node in its left subtree (OR) the smallest node in its right subtree.  Step 3 - Swap both deleting node and node which is found in the above step.  Step 4 - Then check whether deleting node came to case 1 or case 2 or else goto step 2  Step 5 - If it comes to case 1, then delete using case 1 logic.  Step 6- If it comes to case 2, then delete using case 2 logic.  Step 7 - Repeat the same process until the node is deleted from the tree.
• 15.
  Construct a BinarySearch Tree by inserting the following sequence of numbers... 10,12,5,4,20,8,7,15 and 13
• 17.
  In-order Tree traversal •L RO R (a+b) Pre-order Tree traversal • Ro L R (+ab) Post-Order Tree traversal • L R RO (ab+) + a b