Gathering the value of the leaf nodes in a binary tree with a recursive method

2
votes

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;

}

1
javarecursionbinary-search-tree

1 Answers

0
votes

Answer

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));

Explanation :

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

Example

Here's an example with a binary tree with just 6 nodes :

1
 2
  4
  5
 3
  6

and some debugging information :

calling leafNodes(1)
 calling leafNodes(2)
  calling leafNodes(4)
   4 is a leaf
   returning [4] for 4
  calling leafNodes(5)
   5 is a leaf
   returning [5] for 5
  returning [4, 5] for 2
 calling leafNodes(3)
  calling leafNodes(6)
   6 is a leaf
   returning [6] for 6
  returning [6] for 3
 returning [4, 5, 6] for 1

I hope it makes it clearer when calling and returning happens.