Question

Write a non recursive method to insert into an AVL tree in Java

Answer 1

// Here is the requiremd method

public void insertAVL(Key key, val i)

{

// Creating node

// node have key and value parameter

Node node = new Node(Key, i);

// check if empty tree

// if yes, then return value as root

if(root==null)

{

    root = i;

    return;

}

// now, intialie parent value as null

Node parent = null, y=root;

// traverse till the null value of root

while(y!=null)

{

// intializeing value of root to parent

parent = y;

// cretae a variable for result

int result = key.compareTo(y.key);

// check if result is negative

if(result<0){

    // store value in left subtree

    y=y.left;

}

// check if result is positive

else if(result>0){

    // assign value to right subtree

    y =y.right;

}

else{

    y.val=val;

    return;

}

}

// assign value of parent node as result

int result=key.compareTo(parent.key);

// check if result is negative

if(result<0){

parent.left=node;

}

else{

parent.right=node;

}

}