CODEWITHSUNDEEP
flutterdarttreen-ary-tree
Devon L
Devon L

Reputation: 13

Dart : N-ary tree implementation

I have a university project where I need to implement an N-ary tree in dart.

This is my node so far

class Node {

    Node parent; // parent of the current node
    List<Node> children; // children of the current node
    int id;
    String actualMessage;

    Node (int id, String actualMessage){
        this.id=id;
        this.actualMessage=actualMessage; 
        children  = new List<Node>();
    }
}

I am stuck on how I should implement the following methods. I will try to explain what I need with the following example

A is root and has 3 children : B, C and D. B has 2 children: E and F. E has 1 child: G.

Check Tree example here

  1. How to add a root / parent node /child node to the tree => How to add A , B and E
  2. How to remove a node from the tree. => How to remove B. It should remove its children too.
  3. How to retrieve the "actualMessage" of the parent and all possible children when parent is passed as parameter (on a single level) => How to get the actual message on A ? Method should return actual message on B, C and D too
  4. How to retrieve the number of nodes from the longest path => number of nodes from the longest path is the path from root to the last node. It is 4 in my case.
  5. How to retrieve the number of nodes and list of all parents of the tree on any node getting to the root. => number of nodes from G is 4 and list of all parents from G is E, B and A.

Any code or info on how to do the above will be much appreciated. It's my third day where I am stuck on the same thing.

Thank you

Upvotes: 1

Views: 1696

Answers (1)

Sidak
Sidak

Reputation: 1283

Wow, that's a lot you're asking for :P

I've tried out the first 2 requirements and here is the code that can help you fulfil them.

Node root = new Node(0, "A"); // Your root node

I'll be showing the results of a Pre-Order traversal on the tree.

  1. Adding a New Node:
void addNode(Node parent, Node newNode){
  newNode.parent = parent;
  parent.children.add(newNode);
}

After running:

Node b = new Node(1, "B");
addNode(root, b);

Node e = new Node(2, "E");
addNode(b, e);

Pre-order traversal result:

Visited Node A
Visiting child:
Visited Node B
Visiting child:
Visited Node E

This agrees with your structure :D

  1. Removing a Node (and its children), I used the 'actualMessage' as the comparison. You can use whatever you think is better as per your implementation:
void deleteNode(Node treeRoot, String message){
  Node n = treeRoot;
  if(message == n.actualMessage){
    print("Deleted Node " +n.actualMessage);
    n.parent.children.remove(n);
    return;
  }
  for(int i = 0; i < n.children.length; i++){
      deleteNode(n.children[i], message);
  }
}

After Running:

deleteNode(root, "B");

Pre-order traversal result:

Deleted Node B
Visited Node A

Again, Seems to be working fine :D

Ill update this as soon as I get more time

Upvotes: 1

Related Questions