CODEWITHSUNDEEP
javatreekeybinary-search-tree
user4780686
user4780686

Reputation:

Tree Structure Not Correctly Printing Out

I am having trouble with a basic binary search tree that I have created in Java. I am trying to output the tree structure in the console with prepended spaces before a nodes value with respect to how deep the node is.

For some reason my printTree() function is outputting a tree structure that seems slightly backwards. I wouldn't think that (5 0.0) would be indented because it would stay as the root in a basic tree like this.

Below is my function and the output:

Note: c creates the root, s adds a key and value, and xp outputs the tree.

private int k;
private float d;
private Node left, right;

public Node(int k) {
    this.k = k;
}

public Node(int k, float d) {
    this.k = k;
    this.d = d;
}

private int height(Node n) {
    if (n == null)
        return -1;
    return 1 + Math.max(height(n.left), height(n.right));
}

private void printTree(Node n) {
    if (n == null)
        return;
    System.out.println(new String(new char[3 * height(n)]).replace("\0", " ") + "(" + n.k + " " + n.d + ") ");
    printTree(n.left);
    printTree(n.right);
}

Output:

enter image description here

I'm pretty sure that based on my input that 5 should not be indented at all because it would be root node.

I believe that it should look something like (based on a binary search tree):

(5 0.0)
    (4 1.2)
        (2 3.5)
    (6 7.5)
        (87 96.5)

(with the correct amount of prepended spaces of course)

Can anybody explain what I'm doing wrong?

Upvotes: 2

Views: 63

Answers (1)

realitybreeder
realitybreeder

Reputation: 141

You calculate the number of spaces as 3*height(n). height(n) calculates the maximum path length of the left and the right tree, so the root will always be the furthest to the right.

either calculate the height of a node as the length of the path from the node to the root or precalculate the maximum height and set the number of whitespaces for a node to maxHeight - height(n).

Upvotes: 1

Related Questions