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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Data Structures
  3. Balanced Trees
  4. Self Balancing Tree
  5. Discussions

Self Balancing Tree

Problem
Submissions
Leaderboard
Discussions

Sort 162 Discussions, By:

votes

Please Login in order to post a comment

  • hdc1112
    7 years ago+ 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.

    145|
    Permalink
    View more Comments..
  • tomatohakase
    6 years ago+ 1 comment

    Python 3 please

    37|
    Permalink
  • rajp4690
    5 years ago+ 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));
           }
       }
    
    24|
    Permalink
  • rohitashwanigam
    3 years ago+ 0 comments

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

    20|
    Permalink
  • sinfulexp
    6 years ago+ 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.

    10|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature