Tanner - 1 year ago 48

Java Question

I have to make a class for a binary search tree for a school assignment, and one of the methods I must implement is going to return a string of all the leaf node values, separated by a comma, like this ["Leaf node 1",Leaf node 2, Leaf node 3].

Going from left to right.

I have to solve this using a recursive helping method, and I'm totally blank

This is what I have so far

`public void leafNodes(Node<T> n)`

{

if(n.left != null) leafNodes(n.left);

if(n.right != null) leafNodes(n.right);

if(n.left == null && n.right == null)

{

// Do something in here?

}

}

Tried editing after suggestion:

`I tried adding it like this:`

public ArrayList<String> leafNodes(Node<T> n)

{

ArrayList<String> list = new ArrayList<>();

if(n.left != null) leafNoder(n.left);

if(n.right != null) leafNoder(n.right);

if(n.left == null && n.roight == null)

{

list.add(n.value.toString());

}

return list;

}

The method that takes use of this helping method now return an empty string. Or just the "[]".

`public String LeafNodeValues()`

{

StringJoiner sj = new StringJoiner(", ", "[","]");

if(empty()) return sj.toString();

ArrayList<String> a = leafNodes(rot);

for(int i = 0; i < a.size(); i++)

{

sj.add(a.get(i));

}

return sj.toString();

}

Like this?

`public ArrayList<String> leafNodes(Node<T> n)`

{

ArrayList<String> list = new ArrayList<>();

if(n.left != null) list.addAll(leafNoder(n.left));

if(n.right != null) list.addAll(leafNoder(n.right));

if(n.left == null && n.roight == null)

{

list.add(n.value.toString());

}

return list;

}

Answer Source

Your LeafNodes method could return an `ArrayList<String>.`

You begin with an empty List, you addAll leafNodes(n.left), you addAll leafNodes(n.right), and if n is a leaf, you add n to the list. Finally, you return the List.

To get the desired result, you can call leafNodes on the root node, and use :

```
String.join(",", leafNodes(root));
```

In your binary tree, every node has 0 child (a leaf), 1 child or 2 children.

If it is a leaf, its value should be written into a one element list, and returned to the parent node. That's what you do with

`list.add(n.value.toString());`

`return list`

If the node has children, its value should not be added to the list, but some children, grandchildren (or grandgrandchildren or ...) must be leaves, so it needs to pass this list to the parent node. That's what you do with :

`list.addAll(leafNodes(n.left));`

`list.addAll(leafNoder(n.left));`

`return list`