Trees Insert Method

[Malv]

Question :

The insert method takes two parameters, parentVal and childVal and inserts a new node containing childVal as the last child of any node containing parentVal. If there is no node containg parentVal then insert has no effect. insert will not insert a new node below a parent that has a pre-existing child node containing childVal. To illustrate, the call insert(3,3) on the tree:

Root: 1
Child of 1: 3,4

will result in the tree:

Root: 1
Child of 1: 3,4
Child of 3: 3

which, when when given the call insert(3,5) will result in the tree:

Root: 1
Child of 1: 3,4
Child of 3: 3,5
Child of 3: 5

Futher calls with duplicate elements such as insert(3,5) or insert(1,4) will have no effect.


Below is my code and my code does not have the case which after I insert 1,4 and 1,3 , I want to insert 3,3 but it just simply ignores the code. Anyone can tell me which part affects?

public void insert(T parentVal, T childVal){
        insert(root, parentVal, childVal);
    }

    // put any auxiliary methods you may define here.

    private void insert(Node<T> n, T parentVal, T childVal){
        boolean notInserted = true;
        for(int i=0; i<n.children.size(); i++){
            if(n.children.get(i).val.equals(childVal)){
                notInserted = false;
            }
        }
        if(notInserted){
            if(n.val.equals(parentVal)){ // i think its this part.
                Node<T> tmp = new Node<T>();
                tmp.val = childVal;
                n.children.add(tmp);
            }
            for(int i=0; i<n.children.size(); i++){
                insert(n.children.get(i), parentVal, childVal);
            }
        }
}

[JosAH]

I don't understand your algorithm, imho it should be:

- find the parent node; if not found then stop;
- if the new node already a child of parent then stop;
- add new node as child of parent.

kind regards,

Jos

[Malv]

Anymore comment on this ?

[gimbal2]

If you don't understand what JosAH is telling you then say so and ask for clarification, don't just ignore him and ask for other comments.

[Malv]

I understand. Just that he doesn't understand. So i asked for other comments. Don't just assume. Didn't ask for unrelated comment, thanks.

[JosAH]

I understand. Just that he doesn't understand. So i asked for other comments. Don't just assume. Didn't ask for unrelated comment, thanks.

Who doesn't understand what, except for your incorrect algorithm?

Jos

[gimbal2]

I understand. Just that he doesn't understand. So i asked for other comments. Don't just assume. Didn't ask for unrelated comment, thanks.

Then tell Jos you think he's mistaken! Its just rude to flat out ignore someone that is trying to help; I certainly wouldn't want to help anyone that acts like that.

[Malv]

Did you even read through the codes? How incorrect it is? Which part?

[JosAH]

Did you even read through the codes? How incorrect it is? Which part?

You have to give more information w.r.t. the requirements; does the tree contain duplicates? If so, do you want to add the new node to all those duplicates? Is it a search tree? You can't be just vague, hand over an incorrect implementation of an algorithm (otherwise you wouldn't have started this thread) and expect others to do your work and just spoonfeed you. You want a correct implementation, we couldn't care less.

Jos

[Malv]

My question is right above the code. and no the tree does not allow duplicates of parentchild.

[JosAH]

My question is right above the code. and no the tree does not allow duplicates of parentchild.

Then my first suggestion still applies 100%:

- find the parent node; if not found then stop;
- if the new node already a child of parent then stop;
- add new node as child of parent.

You can add one more constraint:

- if the new node is already in the tree (somewhere) then stop;

Jos

[Malv]

- find the parent node; if not found then stop; // if(n.val.equals(parentVal)){
- if the new node already a child of parent then stop; // if(n.children.get(i).val.equals(childVal)){ <- but this only see if n.children contains childVal
- add new node as child of parent.
// Node<T> tmp = new Node<T>();
tmp.val = childVal;
n.children.add(tmp);

You can add one more constraint:

- if the new node is already in the tree (somewhere) then stop; //done

anyway the tree doesnt work in a way where parent and child node can be found.
Here is the full code:

import java.util.*;


/**
   Definition of a tree container that supports insertion 
   by adding the child not correspoinding to a parent node.
*/

public class InsertByParentTree<T>{

 
    private Node<T> root;   // reference to the root of the tree.


    /**
      private class defining a tree node.
    */

    private class Node<T1>{
       
        // data members, value and children.

        public T1 val;
        public ArrayList<Node<T1>> children = new ArrayList<Node<T1>>();

        // zero-argument toString method

        public String toString(){
            return toString("");
        }

        // auxiliary toString method to print the tree in 
        // a nice indented fashion.

        public String toString(String prefix){

            String res = prefix + val + "\n";
            for (Node<T1> x: children){
                res += prefix + x.toString(prefix+" ");
            }
            return res;
        }

    }


   
    /**
       Constructor for InsertByParentTree's. 
       Builds the root node.
       @param val the value to insert at the root node.
    */
    public InsertByParentTree(T val){
        root = new Node<T>();
        root.val = val;
    }


    /**
     Inserts a node containing childVal  at the end of the list
     of childnodes of each node containing parentVal. 
     Does nothing if, parentVal cannot be 
     found in the tree. Will not insert a node under a parent
     containing parentVal if a node containing childVal is already
     an immediate child of childval.
     @param parentVal the data in the parent node to match.
     @param childVal the data to be inserted in a new node
            under the parentVal.
    */
    
    public void insert(T parentVal, T childVal){
        if(root!=null){
            insert(root, parentVal, childVal);
        }
    }

    // put any auxiliary methods you may define here.

    private void insert(Node<T> n, T parentVal, T childVal){
        boolean notInserted = true;
        for(int i=0; i<n.children.size(); i++){
            if(n.children.get(i).val.equals(childVal)){
                notInserted = false;
            }
        }
        if(notInserted){
            if(n.val.equals(parentVal)){
                Node<T> tmp = new Node<T>();
                tmp.val = childVal;
                n.children.add(tmp);
            }
            for(int i=0; i<n.children.size(); i++){
                insert(n.children.get(i), parentVal, childVal);
            }
        }
    }
    
    public static void main(String args[]){
        InsertByParentTree<Integer> myTree = new InsertByParentTree<Integer>(1);
            myTree.insert(1,4);
            myTree.insert(1,3);
            myTree.insert(3,3);
        System.out.println(myTree.toString());
    }

    public String toString(){
        return root.toString();
    }
}

[JosAH]

anyway the tree doesnt work in a way where parent and child node can be found.

Trees don't work; only certain animals do.

Start with a simple (recursive) method Node<T> find(T t) that finds a Node for you (if present). If find(child) returns non-null, there is no need to insert anything because it's already in the tree; otherwise if find(parent) returns non-null, insert your child to the parent.

Jos

[Malv]

Hi Jos,

Has gone through your answer and understood your logic.

However I still have doubts on what to do on the else case. Line 80 to 87

Below is the code:

import java.util.*;


/**
   Definition of a tree container that supports insertion 
   by adding the child not correspoinding to a parent node.
*/

public class InsertByParentTree<T>{

 
    private Node<T> root;   // reference to the root of the tree.


    /**
      private class defining a tree node.
    */

    private class Node<T1>{
       
        // data members, value and children.

        public T1 val;
        public ArrayList<Node<T1>> children = new ArrayList<Node<T1>>();

        // zero-argument toString method

        public String toString(){
            return toString("");
        }

        // auxiliary toString method to print the tree in 
        // a nice indented fashion.

        public String toString(String prefix){

            String res = prefix + val + "\n";
            for (Node<T1> x: children){
                res += prefix + x.toString(prefix+" ");
            }
            return res;
        }

    }


   
    /**
       Constructor for InsertByParentTree's. 
       Builds the root node.
       @param val the value to insert at the root node.
    */
    public InsertByParentTree(T val){
        root = new Node<T>();
        root.val = val;
    }


    /**
     Inserts a node containing childVal  at the end of the list
     of childnodes of each node containing parentVal. 
     Does nothing if, parentVal cannot be 
     found in the tree. Will not insert a node under a parent
     containing parentVal if a node containing childVal is already
     an immediate child of childval.
     @param parentVal the data in the parent node to match.
     @param childVal the data to be inserted in a new node
            under the parentVal.
    */
    
    public void insertChild(Node<T> n, T parentVal, T childVal){
        Node<T> findParent = find(n, parentVal);
        Node<T> findChild = find(n, childVal);
        Node<T> ch = new Node<T>();

        if(n.val.equals(parentVal)){ //finds the correct parentVal and add the childVal to the parentVal
            ch.val = childVal; 
            n.children.add(ch); //adds the childVal into n.children
        }
        /*else{
            // when parentVal == childVal, for example when I insert(3,3), it comes in here
            }
        }*/
        
        for(int i=0; i<n.children.size(); i++){
            if(findChild == null && findParent != null){
                insertChild(n.children.get(i), parentVal, childVal);
            }
            
        }
    }
    
    public void insert(T parentVal, T childVal){
        if(root!=null){
            insertChild(root, parentVal, childVal);
        }
    }
    
        
    private Node<T> find(Node<T>n, T t){
        boolean contains = false;
        Node<T> tmp = new Node<T>();
        for(int i=0; i<n.children.size(); i++){
            if(n.children.get(i).val.equals(t)){
                contains = true;
            }
        }
        if(contains==true){
            tmp.val = t;
        }else{
            tmp.val = null;
        }
        return tmp;
    }
    
    public static void main(String args[]){
        InsertByParentTree<Integer> myTree = new InsertByParentTree<Integer>(1);
            myTree.insert(1,4);
            myTree.insert(1,3);
            myTree.insert(3,3);
        System.out.println(myTree.toString());
    }

    public String toString(){
        return root.toString();
    }
}

[JosAH]

First try to find the child node; if you found it there is no need to continue because the child is already in the tree (no duplicates allowed according to your own requirements); next try to find the parent node; if not found there is also no need to continue (again, according to your own requirements); else add a new child node to the found parent node.

Jos

[Malv]

First try to find the child node; if you found it there is no need to continue because the child is already in the tree (no duplicates allowed according to your own requirements); next try to find the parent node; if not found there is also no need to continue (again, according to your own requirements); else add a new child node to the found parent node.

Jos

sorry jos. sorry for the misunderstanding. you ask me to find the child node. den if i found it, no need to continue but now, i just realise that child can be duplicated. what changes are there to the logic now? when i have already inserted(1,4) in, i cannot insert another (1,4) again, only this cannot be duplicated

[JosAH]

sorry jos. sorry for the misunderstanding. you ask me to find the child node. den if i found it, no need to continue but now, i just realise that child can be duplicated. what changes are there to the logic now? when i have already inserted(1,4) in, i cannot insert another (1,4) again, only this cannot be duplicated

That is never going to work: suppose I insert (1, 2) (1 is the parent of 2), next I insert (2, 1) which is allowed by your requirements and finally I want to insert (1, 3); which one? Better sort out your requirements first before you start asking questions here.

Jos

[Malv]

That is never going to work: suppose I insert (1, 2) (1 is the parent of 2), next I insert (2, 1) which is allowed by your requirements and finally I want to insert (1, 3); which one? Better sort out your requirements first before you start asking questions here.

Jos

Sorry jos for the messy requirements. from your case, insert(1,2), insert(2,1), insert(1,3) . it should work and appear as

1
^2
^^1
^^^3
^3

but if i were to add in 2,2 ?'

it should be

1
^2
^^1
^^2^3
^3

but my output is
1
^2
^^1
^^^3
^3
^2

[JosAH]

Is the requirement: for every potential parent, add the new node as a child; a potential parent is a node that doesn't have the new node as a child yet.

Jos

[Malv]

Is the requirement: for every potential parent, add the new node as a child; a potential parent is a node that doesn't have the new node as a child yet.

Jos

i think so jos? dont really understand what it means thou