The Heap Space

  import java.util.*; // The node of the AVL tree // here we also maintain the height of each node so as to make height adjustments easier after  // the rotation in AVL tree class TreeNode{     int data;     int height;     TreeNode left;     TreeNode right;   // creating a node of AVL tree using constructor // Time Complexity - O(1) , Space Complexity - O(1)     TreeNode(int x){         this.data=x;         this.height=0;         this.left=null;         this.right=null;     }   } public class Main {   // Root of AVL tree     TreeNode root;   // Function to do a level order Traversal of AVL tree // Time Complexity - O(n) , Space Complexity - O(n) [As queue is used]    public void levelOrderTraversal() { //if AVL tree is empty   if (root == null) { ...

  Hence Algorithm of left rotating a node in AVL tree : treeNode leftRotate(cdn){ treeNode NR = cdn.right; cdn.right = NR.left; // any left child of NR will be right child of cdn NR.left = cdn; / / After doing rotation, we have to adjust the height of cdn and NR now cdn.height = calculateHeight(cdn); NR.height = calculateHeight(NR); // finally we will return newRoot to the recursively calling function return NR; } The algorithm of right rotate is just the mirror image of this : treeNode rightRotate(cdn){ treeNode NR = cdn.left; cdn.left= NR.right; // any right child of NR will be left child of cdn NR.right= cdn; / / After doing rotation, we have to adjust the height of cdn and NR now cdn.height = calculateHeight(cdn); NR.height = calculateHeight(NR); // finally we will return newRoot to the recursive...

  If a method returns some node instead of void, I am going to wrap that method like this : insert node function ->   public treeNode addNode(treeNode root, int data ) {                                                 .......................................................                                                  .......................................................                                                  ........................................................                                   ...

Insertion in Binary Search Tree : public treeNode insertNode(Node currentNode, int data) { if(currentNode==null){ currentNode = new treeNode(data); } // data moves to right subtree if(data> currentNode .data){ currentNode .right = insertNode( currentNode .right,data);  } //data moves to left subtree else if(data<= currentNode .data){ currentNode .left = insertNode( currentNode .left,data); } return currentNode ; } Deletion of a node in Binary Search Tree: public  treeNode deleteNode(treeNode node, int data){ if(root==null) // tree is empty return null; if(data<node.data){ node.left = deleteNode(node.left,data); } else if(data>root.data){ node.right = deleteNode(node.right,data); } // if the current node has the data to delete, consider three cases - 0/1/2 child of current node // if two child // find the minimum of the right subtree and replace the current no...