need to display flow full binary tree in java

Question

There is basically the same question on this site except it says dont post questions to questions here is a link. Binary Tree Recursive Function

I need to print out a binary tree that looks like this but for an arbitrary size:

--------x-------
----x-------x---
--x---x---x---x-
-x-x-x-x-x-x-x-x 
xxxxxxxxxxxxxxxx

however when i execute the code outputs errors along with an endless print

:::X:::::X::X:XXXXX

and there is a blue line under this which i can click on and it brings up a window saying "source not found for" with endless X's

at sun.nio.cs.SingleByte.withResult(Unknown Source)
at sun.nio.cs.SingleByte.access$000(Unknown Source)
at sun.nio.cs.SingleByte$Encoder.encodeArrayLoop(Unknown Source)
at sun.nio.cs.SingleByte$Encoder.encodeLoop(Unknown Source)
at java.nio.charset.CharsetEncoder.encode(Unknown Source)
at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
at sun.nio.cs.StreamEncoder.write(Unknown Source)
at java.io.OutputStreamWriter.write(Unknown Source)
at java.io.BufferedWriter.flushBuffer(Unknown Source)
at java.io.PrintStream.write(Unknown Source)
at java.io.PrintStream.print(Unknown Source)
at BinaryBuilder.display(BinaryBuilder.java:25)
at BinaryBuilder.display(BinaryBuilder.java:31)
at BinaryBuilder.display(BinaryBuilder.java:31)

the code i have so far is just not working properly and i have had problems with recursion and understanding the order of the stack frames executing. Please help i thought i was on the right track using the row to return from the recursion. I need some guidance and a push in the right direction :)

    import java.util.Scanner;
public class BinaryBuilder {
    int levels = 0;
    int width = 0;
    int leaves = 0;
    Scanner sn = new Scanner(System.in);
    public BinaryBuilder() {
        //prt("how many leaves?");
        //leaves = sn.nextInt();
        //levels = (int)Math.sqrt((double)leaves);
    }
    public void setLevelLeaves(int l,int le){
        levels = l;
        leaves = le;
    }

    public void display(int left, int right, int row){
        int i =left;
        int mid = (left+right)/2;           //maybe a +1
        if(row>levels){
            return;
        }
        while(i <= right){
            if(i==mid){
                System.out.print("X");
            }else{
                System.out.print(":");
            }
            i++;
        }
        display(left, mid, row++);
        display(mid, right, row++);
    }

    public void prt(String n){
        System.out.println(n);
    }

}

Main

public class PartBTest {

    public PartBTest() {
    }

    public static void main(String[] args) {
        BinaryBuilder bb = new BinaryBuilder();
        //bb.prt("width will be reduced to a factor of 2");
        bb.setLevelLeaves(3, 8);
        bb.display( 0, bb.leaves-1, 0);
    }

}

Happy coding :}

Answer 1

Woah!

Sorry for the late response, kinda got caught up in some games, but I finally got this out.

import java.util.Scanner;

public class Testing {

    public static void main(final String[] args) {

        final Scanner in = new Scanner(System.in);

        System.out.print("How many rows would you like?");

        final int rows = in.nextInt();
        int mod = (1 << (rows - 1)) - 1;

        for(int i = 0; i < rows; i++){
            for(int j = 0; j < mod; j++){
                System.out.print("-");
            }
            System.out.print("X");
            for (int j = 0; j < (1 << i) - 1; j++){
                for(int k = 0; k < 2 * mod + 1; k++){
                    System.out.print("-");
                }
                System.out.print("X");
            }
            for(int j = 0; j < mod; j++){
                System.out.print("-");
            }
            mod >>= 1;
            System.out.println();
        }

        in.close();

    }

}

This is a pretty straight-forward logical approach. It uses the fundamentals of powers of 2 and binary to calculate what needs to be done and how it should be done. As you can see, the first row would have 0b1 X's, the second would have 0b10 X's and so on. From there, you can also see the amount of dashes needed before an x. If there are 4 rows, the first row needs 0b111 dashes, second needs 0b11. From there, it just repeats doing the opposite decay of the number of dashes. First one needs 0 repeats, second needs 1.

If you need any more explaining on this I would be happy to do so.

Edit 1: More Explaining

For the following explanation I will use rows = 4 for the analysis. Therefore, the output should resemble:

-------X-------
---X-------X---
-X---X---X---X-
X-X-X-X-X-X-X-X

Let's break down a single line. Using the second as an example we can come to the conclusion that the logic flow is:

1. Print out buffer (In this case 3 dashes) -> ---
2. Print out lone x -> ---x
3. Print out repeating section n times. n = 1, (-------x) -> ---x-------x
4. Print out buffer (3 dashes again) -> ---x-------x---

This can be replicated for all of the cases.

First case: buffer = 7, n = 0 -> no repeating section generated since n=0
Second case: buffer = 3, n = 1, dashes in buffer = 7
Third case: buffer = 1, n = 3, dashes in buffer = 3
Fourth case: buffer = 0, n = 7, dashes in buffer = 1

You can see in all of these cases the variables are all related to a power of 2 minus one (Mersenne primes).

Using that technique, we come to the conclusion of some basic formulas:

(1 << (rows - 1)) - 1) uses the amount of rows (4) to shift a value of 0001 to 1000, then subtracts one, 0111 leaving us with 7, the initial buffer.

(1 << i) - 1 uses the current row we are on (ranging 0-3) to produce the repeated amount of times.Plugging in 0, 1, 2 and 3 into that formula we get respectively: 0, 1, 3, 7 (The amount of times the middle section is repeated per row)

2 * mod - 1 used to calculate the amount of dashes in the 'middle section' used in the formula above

mod >>= 1 shifts the mod right. This allows the first formula to go from initial value of 7, to 3, to 1 and then to 0.

Answer 2

Trying to display the outputs directly makes your recursion cumbersome. Also, you may want to rethink your parameters. I believe that leaf count should be enough.

I would do it differently, by returning a List of strings for every call, instead of printing the output right away. This way you can implement your main method by running it with {leaf count}/2, merging the list with itself (by concatenating rows in the same index), and then adding a new header row for the root.

---

Following is my solution. Note that it only accepts an argument which is a power of 2:

public static List<String> buildTree(int leafs) {
    if (leafs == 1)
        return Arrays.asList("x");

    // Recursive call
    List<String> subTree = buildTree(leafs/2);

    ArrayList<String> merged = new ArrayList<String>();
    // Add new header
    String blanks = String.format("%-" + (leafs/2) + "s", "").replace(' ', '-');
    String header = blanks + "x" + blanks.substring(1);
    merged.add(header);

    // Duplicate subtree
    for (String row : subTree)
        merged.add(row + row);

    return merged;
}