We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Balanced Trees
  4. Self Balancing Tree
  5. Discussions

Self Balancing Tree

Sort 162 Discussions, By:

  • hdc1112
     + 35 comments

    Just want to let everyone know that in this question, the height of a "null" node is -1 INSTEAD OF 0, and the height of the leaf node is 0 INSTEAD OF 1. The latter will let you pass several cases, while the former will let you pass every case.

  • tomatohakase
     + 1 comment

    Python 3 please

  • rajp4690
     + 3 comments

    JAVA Solution

    static Node insert(Node root,int val) {
       if(root == null) {
           root = new Node();
           root.val = val;
           root.ht = setHeight(root);
           return root;
       }
       if(val <= root.val) {
           root.left = insert(root.left, val);
       }
       else if (val > root.val) {
           root.right = insert(root.right, val);
       }
       int balance = height(root.left) - height(root.right);
       
       if(balance > 1) {
           if(height(root.left.left) >= height(root.left.right)) {
               root = rightRotation(root);
           }
           else {
               root.left = leftRotation(root.left);
               root = rightRotation(root);
           }
       }
       else if(balance < -1) {
           if(height(root.right.right) >= height(root.right.left)) {
               root = leftRotation(root);
           }
           else {
               root.right = rightRotation(root.right);
               root = leftRotation(root);
           }
       }
       else {
           root.ht = setHeight(root);
       }
       return root;
   }

   private static Node rightRotation(Node root) {
       Node newRoot = root.left;
       root.left = newRoot.right;
       newRoot.right = root;
       root.ht = setHeight(root);
       newRoot.ht = setHeight(newRoot);
       return newRoot;
   }

   private static Node leftRotation(Node root) {
       Node newRoot = root.right;
       root.right = newRoot.left;
       newRoot.left = root;
       root.ht = setHeight(root);
       newRoot.ht = setHeight(newRoot);
       return newRoot;
   }

   private static int height(Node root) {
       if(root == null)
           return -1;
       else 
           return root.ht;
   }

   private static int setHeight(Node root) {
       if(root == null) {
           return -1;
       } 
       else {
           return 1 + Math.max(height(root.left), height(root.right));
       }
   }

  • rohitashwanigam
     + 0 comments

    Why is there no Python editor for this problem ???????

  • sinfulexp
     + 0 comments

    This challenge took me more than 2 days... unbelievable. I was trying to use recursion but I didn't have the option to write another function. 2 days later, I finally realize how to use the balance factor to determine how to rotate. I think my method is a little strange, but I am glad it works. I spend 4 hours debugging case 10 because I could not draw out the tree and had to keep guessing what was wrong with it. My problem with case 10 was, I did not properly update my height after rotating, resulting in my tree having 2 balance factor that was -2 and 2. After the first balance, the 2nd one should become 1 depth lower. Tips: definitely rotate base on balance factor. This method is very efficient in my opinion. 1 or 2 rotation and the insertion becomes perfectly balanced. The example tells you exactly how to rotate it Check for balanced insertion.

Load more conversations