Ошибка при создании сбалансированного бинарного дерева с использованием Java

Question

Я написал этот код для создания binary tree но похоже, что этот код создает unbalanced binary tree, Узлы попадают только на right поддерево root, я получил Null pointer exception если я пытаюсь получить доступ к дочерним узлам левого поддерева. Я хочу создать balanced binary tree с узлами вставляются из left to right, Какую ошибку я здесь делаю и как ее исправить?

public class binTree {

    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    public TreeNode root;

    public binTree(){
        this.root = null;

    }

    public void insert(int data){
        root = insert(root,data);
    }
    public TreeNode insert(TreeNode node,int data){

        if(node == null){
            node = new TreeNode(data);
            //root = node;
        }
        else{
            if(node.left == null){
                node.left = insert(node.left,data);
            }
            else{
                node.right = insert(node.right,data);
            }
        }
        return node;

    }


    public static void main(String args[]){
        binTree obj = new binTree();

        obj.insert(5);
        obj.insert(11);
        obj.insert(13);
        obj.insert(1);
        obj.insert(7);
        obj.insert(21);
        obj.insert(35);
        System.out.println(obj.root.right.left.val);
        System.out.println(obj.root.left.right.val); // this throws null pointer exception
    }

}

Answer 1

Вам нужно будет хранить количество элементов для каждого поддерева в каждом узле дерева следующим образом:

public class BinTree {

    private TreeNode root;

    public static class TreeNode {

        public int val;
        public int elements = 0;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    public BinTree() {
        this.root = null;
    }

    public void insert(int data) {
        root = insert(root, data);
    }

    private static int height(TreeNode node) {
        int result = 0;
        if (node != null) {
            result++;
            int total = node.elements;
            int heightElements = 2;
            while (total > heightElements) {
                total -= heightElements;
                heightElements *= 2;
                result++;
            }
        }
        return result;
    }

    public TreeNode insert(TreeNode node, int data) {
        if (node == null) {
            node = new TreeNode(data);
        } else if (height(node.left) == height(node.right)) {
            node.left = insert(node.left, data);
        } else {
            node.right = insert(node.right, data);
        }
        node.elements++;
        return node;
    }

    public static void main(String args[]) {
        BinTree obj = new BinTree();
        obj.insert(5);
        obj.insert(11);
        obj.insert(13);
        obj.insert(1);
        obj.insert(7);
        obj.insert(21);
        obj.insert(35);

        System.out.println(obj.root.val);
        System.out.println(obj.root.left.val);
        System.out.println(obj.root.right.val);
        System.out.println(obj.root.left.left.val);
        System.out.println(obj.root.left.right.val);
        System.out.println(obj.root.right.left.val);
        System.out.println(obj.root.right.right.val);
    }
}