CODEWITHSUNDEEP
javarecursionbinary-search-tree
user202542
user202542

Reputation: 211

Balance a binary search tree

I'm trying to implement a binary search tree class in Java with a method that can rebalance the tree if there's a difference in height. I'm trying to do it by first storing the value of the nodes in an List (an attribute of the class).

I then want to take the middle element of this list and assign this to the root of the tree. After this I take the left- and right part of the list and do the same thing recursively to the left- and right children of the root and so on.

My algorithm doesn't seem to work though and I don't understand what I'm doing wrong. I wonder if someone can take a look at my code and explain what the problem is? What I do is basically pass the ordered list of elements of the tree (an attribute of the class) and the root into the function below:

public void build(BinaryNode<E> n,List<E> list) {
    int idx = (int)Math.floor(list.size()/2);
    if(n!=null) {
        n.element = list.get(idx);
    } else if(n==null) {
        n = new BinaryNode<E>(list.get(idx));
    }

    if(!list.subList(0,idx).isEmpty()) {
        build(n.left,list.subList(0,idx));
    } 

    if(!list.subList(idx+1,list.size()).isEmpty() ){
        build(n.right,list.subList(idx+1,list.size()));
    }
    return;
}

Kind regards,

Upvotes: 0

Views: 476

Answers (2)

Yair Landmann
Yair Landmann

Reputation: 69

Try investigating about AVL tree

Some useful links: https://en.wikipedia.org/wiki/AVL_tree https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

Upvotes: 1

Henry
Henry

Reputation: 43728

Java method calls are "call by value". This means changing a parameter (like n in your case) has no effect outside of the method.

Try to define your method like this

public BinaryNode<E> build(List<E> list) { ... }

Upvotes: 1

Related Questions