Печать BinaryTree, отсортированная по значению

Question

public class Tree {
protected class Node {
    Integer val;
    Node[] leaves;

    Node(int v, int grad) {
        val = v;
        leaves = new Node[grad];
    }
}

int counter = 1;
int grad;
int height;
protected Node root;

public Tree(int grad, int hoehe) throws IllegalArgumentException {
    if (grad < 0)
        throw new IllegalArgumentException("Grad < 0");
    if (hoehe < 0)
        throw new IllegalArgumentException("Hoehe < 0");
    if (grad == 0 && hoehe > 1)
        throw new IllegalArgumentException("Grad = 0 && Hoehe > 1");
    root = new Node(0, grad);
    inOrderCreate(root, hoehe, grad);
    this.height = hoehe;
    this.grad = grad;
}

public void inOrderCreate(Node root, int height, int grad) {
    if (root != null && height > 1) {
        for (int j = 0; j < root.leaves.length; j++) {
            if (root.leaves[j] == null)
                root.leaves[j] = new Node(0, grad);
            else {
                for (int i = 0; i < root.leaves[j].leaves.length; i++) {
                    root.leaves[j].leaves[i] = new Node(0, grad);
                }
            }
            inOrderCreate(root.leaves[j], height - 1, grad);
        }
    }
}

public int heightOfTree(Node node) {
    if (node == null) {
        return 0;
    } else {
        int max = 0;
        for (Node n : node.leaves) {
            if (heightOfTree(n) > max)
                max = heightOfTree(n);
        }
        return 1 + max;
    }
}

public int maxNode(Node node) {
    int nodeCount = 0;
    for (int i = 0; i < heightOfTree(node); i++) {
        nodeCount += Math.pow(node.leaves.length, i);
    }
    return nodeCount;
}

public int maxLeaf(Node node) {
    return (int) Math.pow(node.leaves.length, heightOfTree(node) - 1);
}

public int maxLeaves() {
    return maxLeaf(root);
}

public int maxNodes() {
    return maxNode(root);
}

public void printMaxNodesAndLeafs() {
    System.out.println("Baum des Grades " + grad + " mit der Hoehe " + height);
    System.out.println("---------------------------------");
    if (root == null) {
        System.out.println("maximale Anzahl von Knoten: 0");
        System.out.println("maximale Anzahl von Blaettern: 0\n");
    } else {
        System.out.println("maximale Anzahl von Knoten: " + maxNodes());
        System.out.println("maximale Anzahl von Blaettern: " + maxLeaves() + "\n");
    }
}

public void filling(Node n) {
    if (n != null) {
        n.val = counter;
        counter++;
        for (int j = 0; j < n.leaves.length; j++) {
            filling(n.leaves[j]);
        }
    }
}

Этот метод заполнит двоичное дерево натуральными значениями.

public void fill() {
    counter = 1;
    if (root != null) {
        root.val = counter;
        counter++;
        for (int j = 0; j < root.leaves.length; j++) {
            filling(root.leaves[j]);
        }
    }
}

public void inOrderSearch(Node p, int val) {
    if (p != null) {
        if (heightOfTree(p) == val) {
            for (int i = (int) ((Math.pow(grad, heightOfTree(p) - 1)) * grad) - 1; i > 0; i--) {
                System.out.print(" ");
            }
            System.out.print(p.val);
        }
        for (int j = 0; j < p.leaves.length; j++) {
            if (j != 0)
                System.out.print(" ");
            inOrderSearch(p.leaves[j], val);
        }
    }
}

Это мой метод печати, который должен печатать все значения по порядку.

public void printTree() {
    Node p = root;
    if (p != null) {
        for (int i = heightOfTree(p); i > 0; i--) {
            inOrderSearch(root, i);
            System.out.print("\n");
        }
    }
}

}

Но, как вы можете на следующих изображениях, печать не симметрична.

Это должен быть вывод этого кода:

Но мой вывод здесь такой, 10 и 12 должны быть симметричными: