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
– default locale, Commented Oct 25, 2016 at 5:28
Are you talking java.util.TreeSet or your own tree set implementation? In the latter case, what does it look like? — Anonymous
– Anonymous, Commented Oct 25, 2016 at 6:01
Doing it without the caller instantiating nodes, isn’t that just a matter of encapsulating the tree creation? — Anonymous
– Anonymous, Commented Oct 25, 2016 at 6: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
– Ham Lingo, Commented Oct 25, 2016 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). — Anonymous
– Anonymous, Commented Oct 25, 2016 at 14:27

Anonymous · Accepted Answer · 2016-10-25 16:54:31Z

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.

Collectives™ on Stack Overflow

Print any given binary TreeSet by level -Java

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related