Created
May 8, 2019 20:17
-
-
Save anandpathak/5f4b100f27aa0e4acf02ed6364cb17f6 to your computer and use it in GitHub Desktop.
convert LinkedList into AVL tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for singly-linked list. | |
* public class ListNode { | |
* int val; | |
* ListNode next; | |
* ListNode(int x) { val = x; } | |
* } | |
*/ | |
/** | |
* Definition for a binary tree node. | |
* public class TreeNode { | |
* int val; | |
* TreeNode left; | |
* TreeNode right; | |
* TreeNode(int x) { val = x; } | |
* } | |
*/ | |
class AvlTree { | |
TreeNode root = null; | |
public TreeNode sortedListToBST(ListNode head) { | |
while(head!=null){ | |
this.root = insert(head.val, this.root); | |
head = head.next; | |
} | |
return this.root; | |
} | |
public TreeNode leftRotate(TreeNode t){ | |
TreeNode newNode = t.right; | |
t.right = newNode.left; | |
newNode.left = t; | |
return newNode; | |
} | |
public TreeNode rightRotate(TreeNode t){ | |
TreeNode newNode = t.left; | |
t.left = newNode.right; | |
newNode.right = t; | |
return newNode; | |
} | |
public TreeNode insert (int val, TreeNode root){ | |
if(root ==null){ | |
return new TreeNode(val); | |
} | |
else if( root.val > val){ | |
root.left = insert(val, root.left); | |
} else { | |
root.right = insert(val,root.right); | |
} | |
// check if balance is greater than 2 | |
if(balance(root) > 1) { | |
if(balance(root.left) < 0 ) | |
root.left = leftRotate(root.left); | |
root = rightRotate(root); | |
} else if( balance (root) < 1 ){ | |
if(balance(root.right) > 0) | |
root.right = rightRotate(root.right); | |
root = leftRotate(root); | |
} | |
//displayNode(root); | |
return root; | |
} | |
//get balance of tree | |
public int balance(TreeNode t){ | |
return height(t.left) - height(t.right); | |
} | |
// calculate height of the tree | |
public int height(TreeNode t){ | |
if(t==null) | |
return 0; | |
else | |
return 1+ max(height(t.left), height(t.right)); | |
} | |
public int max( int a ,int b){ | |
return (a > b) ? a : b; | |
} | |
public void displayNode(TreeNode root){ | |
if(root == null) | |
return; | |
System.out.print(" "+root.val); | |
displayNode(root.left); | |
displayNode(root.right); | |
// System.out.print(""+root.val+ "["); | |
// displayNode(root.left); | |
// displayNode(root.right); | |
// System.out.print("]"); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment