I found in different places on the internet how to turn a Binary Search Tree into an AVL tree in O(nlog(n)). I was wondering how can this be done in O(n) (as the worst case limit). It kinda seems possible with right rotations but I just don't know how to implement it exactly. Any idea is welcomed.

  • 1
    Walk the BST and insert each node into an AVL. That's O(n). – Robert Harvey Apr 14 '16 at 15:21
  • 1
    @RobertHarvey Walking a BST is O(n) but each insertion is O(log n) for an AVL tree, leading to O(n log n). – amon Apr 14 '16 at 15:27
  • 1
    Insertion into on AVL tree is O (log n) only because you have to find where to insert nodes and rebalance things. But if you have a binary search tree then you know the exact order in which to insert the nodes. No searching needed. For example, if you have 48 nodes, then your AVL tree consists of node 24 at the top, an AVL tree with nodes 0 to 23 at the left, and an AVL tree with nodes 25 to 47 at the right. No searching, no rebalancing. – gnasher729 Apr 14 '16 at 16:18

If you don't care about using extra memory then you can dump out the BST into a sorted array. Then you can balance the new tree perfectly.

tree balance(int[] array){
    if(array.length == 0) return null;

    Node n = new Node(array[$/2]);
    n.left = balance(array[0..$/2]);
    n.right = balance(array[$/2+1..$]);
    return n;

This still needs to have the balance factor added.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.