Print any given binary TreeSet by level -Java

Question

I've seen a lot of questions (How to print binary tree diagram?) about how to print out a Tree by level and they all seem to be using nodes, but in the main they define each node and give it specific pointers by hand...I'm looking for a way to do the same thing, print out a tree by level, but you're given a TreeSet of type Integer (e.g. {3,12,28,40,41,58,83}), and you don't know what's going to be in it until runtime.

For simplicity, output would look something like this:

40
12    58
3    28    41    83

With or without the use of Nodes is fine, but I'd be interested to see a version without them.

EDIT:

To clarify, I'm talking about java.util.TreeSet.

So I've been working on this since I posted it, and I came up with a method I call getRoot which takes a TreeSet<Integer> as a parameter and returns an Integerwhich is the middle of the Tree. So for instance if you called it on the example tree, it would return 40.

So now I'm thinking there's probably a way to recursively do what I'm talking about, by calling getRoot on sub trees, e.g. tailSet and headSet of a tree, if that makes any sense. I'm having trouble making it follow through every branch of the tree, however. My code so far:

public TreeSet<Integer> recursivePlease(TreeSet<Integer> t){
        if (t.size()<=1){ //base case
            System.out.println(t.first());
            return t;
        }else{
            System.out.println(getRoot(t));
            return recursivePlease((TreeSet<Integer>) t.headSet(getRoot(t)));
        }
    }

and this...works. But it just prints the left side of the tree. Any help on making this method print the whole tree, or other ideas entirely, are greatly appreciated.

Inner structure of TreeSet is an implementation detail. AFAIK, specification defines time cost/complexity and ordering in TreeSet, but different implementations are free to use different tree structures to achieve this. Could you please specify what kind of a tree do you expect as an answer? — default locale, Oct 25 '16 at 05:28
Are you talking `java.util.TreeSet` or your own tree set implementation? In the latter case, what does it look like? — Ole V.V., Oct 25 '16 at 06:01
Doing it without the caller instantiating nodes, isn’t that just a matter of encapsulating the tree creation? — Ole V.V., Oct 25 '16 at 06:06
@Ole Yeah, I'm talking about `java.util.TreeSet`. And as for your comment about encapsulating the tree creation -- I'm kind of new to java and I'm not really sure what that means. Could you explain more? thanks!! — Ham Lingo, Oct 25 '16 at 14:00
`java.util.TreeSet` encapsulates a `NavigableMap` which probably encapsulates a tree somewhere. So getting to know the structure of that tree — is probably either hard or impossible, sorry. I don’t think you’ll even find out which element is at the root (that is, should be printed in the first line). — Ole V.V., Oct 25 '16 at 14:27
You may want to direct your search engine in the direction of ‘encapsulation’. It’s a core concept in structuring program bigger than school assignments. For `TreeSet`, it already encapsulates the tree creation: when creating a `TreeSet` of the seven elements you mentioned, you couldn’t come to touch a node if you tried. On the other hand, this is your problem when you want to print the tree, because you need the nodes to do so. — Ole V.V., Oct 25 '16 at 15:07
Your code in the edit — is an excellent starting point! I wonder if and how your `getRoot()` really gets the root of the tree, but if you’re happy with what it returns, you should be able to make the rest work. — Ole V.V., Oct 25 '16 at 15:28

score 1 · Accepted Answer · answered Oct 25 '16 at 16:54

Your code is an excellent starting point. Your problem with printing only the left side of the tree comes from the fact than from the second line you have to print two trees, on the third line up to four trees, which your method cannot handle since it only takes one tree as argument. So we will have to alter it to take any number of trees. I have chosen a List<SortedSet<Integer>> (where SortedSet is one of the interfaces that TreeSet implements). This entails rewriting a part of the logic in the method to deal with more trees of course. I didn’t see the need for returning anything, so I changed the return type to void. Here’s what I ended up with:

public void recursivePlease(List<SortedSet<Integer>> trees) {
    List<SortedSet<Integer>> nextLevelTrees = new ArrayList<>();
    for (SortedSet<Integer> t : trees) {
        if (t.size() <= 1) { //base case
            System.out.print("" + t.first() + ' ');
        } else {
            Integer root = getRoot(t);
            System.out.print("" + root + ' ');
            SortedSet<Integer> headSet = t.headSet(root);
            if (! headSet.isEmpty()) {
                nextLevelTrees.add(headSet);
            }
            SortedSet<Integer> tailSet = t.tailSet(root + 1);
            if (! tailSet.isEmpty()) {
                nextLevelTrees.add(tailSet);
            }
        }
    }
    System.out.println();
    if (! nextLevelTrees.isEmpty()) {
        recursivePlease(nextLevelTrees);
    }
}

For the first call you have only a single tree, so you may call it as:

    recursivePlease(Collections.singletonList(t));

On my computer it prints:

40 
12 58 
3 28 41 83

Depending on your getRoot() your result may differ.

Print any given binary TreeSet by level -Java

1 Answers1