Skip to content

Instantly share code, notes, and snippets.

@anandpathak
Created May 8, 2019 20:17
Show Gist options
  • Save anandpathak/5f4b100f27aa0e4acf02ed6364cb17f6 to your computer and use it in GitHub Desktop.
Save anandpathak/5f4b100f27aa0e4acf02ed6364cb17f6 to your computer and use it in GitHub Desktop.
convert LinkedList into AVL tree
/**
* 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