CODEWITHSUNDEEP
javaalgorithmrecursiontree
user1766888
user1766888

Reputation: 409

Finding Maximum of n-ary tree

I have an n-ary tree defined by the short NTN class of 

public class NTN P {
     public int value;
     public Set<NTN> children;
 }

I want to find the maximum of such an n-ary tree. Let's say it's a simple integer n-ary tree with the values: [parent: 1 children: 2, 3, 4] [parent: 2 children: 5, 6] [parent: 4 children 7, 8, 9] the maximum would simply be 9. I'm not sure how to begin writing a method to find the maximum with the prototype:

public static int maximum(NTN t);

From what I've tried:

public static int maximum(NTN t) {
  int max = 0;
      for (NTN e : t.children) {
          if (e.value > max)
              max = e.value;
      }

  return max;
}

The code above would return a maximum of 4 which means it only checks for the children of t but not the subsequent set of children. In this case it won't check the children set of 4, [7,8,9] and 2, [5,6]. How can I change it so that the method finds the maximum of all subsequent children?

Upvotes: 2

Views: 4507

Answers (5)

Ishan Pandey
Ishan Pandey

Reputation: 1

Following code retruns complete node with maxm value from a nary tree

// Following is the given Tree node structure.

template 

class TreeNode
 {
    public:
        T data;
        vector<TreeNode<T>*> children;

        TreeNode(T data) {
            this->data = data;
        }

        ~TreeNode() {
            for (int i = 0; i < children.size(); i++) {
                delete children[i];
            }
        }
 };



TreeNode<int>* maxDataNode(TreeNode<int>* root) {

    if(root == NULL) return NULL;
    TreeNode<int>* maxNode = new TreeNode<int>(0);
    int max = 0;

    for(int i=0; i<root->children.size();i++){
        if(maxDataNode(root->children[i])->data > max)
        {    
            max = maxDataNode(root->children[i])->data;
            maxNode = maxDataNode(root->children[i]);
        }
    }
    if(root->data > maxNode->data)
    {
        maxNode = root;
        return maxNode;
    }
    return maxNode;

}

Upvotes: 0

Melad Basilius
Melad Basilius

Reputation: 4306

public static int maximum(NTN t) {
    int max = t.value;
    Set<NTN> children = t.children;
    if (children != null && !children.isEmpty) {
        for (NTN e : children) {
            max = Math.max(max, maximum(e));
        }
    }
}

Upvotes: 0

Alireza
Alireza

Reputation: 4516

I guess something like this would help , you're doing sth like a DFS on your tree to traverse all the nodes and you look at each nodes value , if it's larger than the max you're keeping as a static variable within you're public class (e.g public static int max) , you set max to be the value of that node , something like this would do (hopefully , not tested, notice that return type is void and you directly update a variable inside your public class) : 

     public void maximum(NTN T){
            if (!T.children.isEmpty() && T.children != null){
                for(NTN e: T.children)
                    maximum(e)
            }
            if (PUBLIC_CLASS.MAX < T.value)
                PUBLIC_CLASS.MAX = T.value;
        }

Upvotes: 0

npinti
npinti

Reputation: 52185

Your solution is not Recursive, so it won't keep going in your sub children, if any. You might want to take a look at Tabu Search. An easier approach (but prone to get stuck in a local maximum) would be Hill Climbing.

Upvotes: 1

Iqbal Djulfri
Iqbal Djulfri

Reputation: 708

public static int maximum(NTN t) {
  int max = t.value;
  Set<NTN> children = t.children;

  // only check if this node is not a leaf
  if (children != null && !children.isEmpty) {
    for (NTN e : children) {
      // here is the recursion
      int maxNext = maximum(e);

      if (maxNext > max) max = maxNext;
    }
  }

  return max;
}

hope this helps :)

Upvotes: 2

Related Questions