CODEWITHSUNDEEP
java
BigO
BigO

Reputation: 15

How to create recursive add method for tree

I have a tree implementation only with two fields:

public class Tree {
    private final String name;
    private final List<Tree> children;

    public Tree(String name) {
        this.name = name;
        this.children = new ArrayList<>();
    }

How to implement the add method, with a recursion? This method inserts a new node into the current tree by the name of the node.

public void add(Tree newNode, String parentName) {
    if (parentName.equals(this.name)) {
        this.children.add(newNode);
    } 
}

Upvotes: 0

Views: 302

Answers (2)

Ryan
Ryan

Reputation: 1760

public class Tree {
private String name;
private List<Tree> children;

private Tree(String name) {
    this.name = name;
    this.children = new ArrayList<>();
}

public boolean add(Tree newNode, String parentName) {
    if (name.equals(parentName)) {
        children.add(newNode);
        return true;
    }
    for (Tree child : children) {
        if (child.add(newNode, parentName)) {
            return true;
        }
    }
    return false;
}

public String output(int level) {
    StringBuilder buff = new StringBuilder();
    
    if (level > 0 ) {
        buff.append('|');
    }
    for (int i = 0; i < level; i++) {
        buff.append("---");
    }
    buff.append(name).append(System.lineSeparator());
    
    for (Tree child : children) {
        buff.append(child.output(level + 1));
    }
    
    return buff.toString();
}
public static void main(String [] args) {
    Tree tree = new Tree("A");
    tree.add(new Tree("B"), "A");
    tree.add(new Tree("C"), "B");
    tree.add(new Tree("1"), "C");
    tree.add(new Tree("2"), "B");
    
    System.out.println(tree.output(0));
}

}

Upvotes: 1

Berlm
Berlm

Reputation: 467

I am assuming this is what you want:

root
|- node1
| |- node2
|
|- node3

Adding node4 to node2 would result in:

root
|- node1
| |- node2
| |  |- node4
|
|- node3

To do so, you will have to implement Breadth First Search or Depth First Search. Either are applicable to your data structure, so I would recommend googling and finding out how these work!

Upvotes: 1

Related Questions