Recursion in Objects

[ARaza110]

public class cation {

   
    public static void main(String[] args) {
        
        new cation().run();
    }
    
        public void run(){
        harada hara=new harada();
    insert(hara);
    insert(hara);
    }
        public void insert(harada hara){
            
        if(hara.left==null){
            hara.left=new harada();
        }
        else{
            insert(hara.left);
        }
    }
        class harada{
            harada left;
public harada(){}


}
}

Can someone please explain, recursion in objects as seen in the above code. I don't understand when i pass "hara.left in else condition", it passes it as if it were a new reference and therefore treats it null and makes a new instance of 'hara.left'. The problem is tht the if condition had already been called and the instance of 'hara.left' was already made!!

Thanks.

[Zaad]

The point u should really note is this that in the class

harada

the variable left is another instance variable of

harada

and when you pass in the insert of the else condition you are passing

hara.left

which is not an initialized instant of the "harada" class. So it goes it into the if condition and initializes it.
nOTE : "hara is instantiated but not hara.left"

[ARaza110]

if(hara.left==null){
hara.left=new harada();
}

Please look hara.left is also initialized in if condition above. So the instance of hara.left was made as well, and the hara.left was already called once!!

[Taywin]

In line 24, your "harada" class variable "left" is NOT initialized. When you create "hara" in your caller (main() method), the "hara.left" is not initialized yet. Then you try to call insert from the main(). Therefore, you cannot compare "hara.left" in your "insert()" method... I think that what Zaad intended to tell you.

To solve this, update your line 24 to harada left=null;

[ARaza110]

public class BinaryTreeExample {
     
    public static void main(String[] args)
     
    {
    new BinaryTreeExample().run();
    }
     
    static class Node
    {
     
    Node left=null;
    Node right;
    int value;
     
    public Node(int value) {
    this.value = value;
    }
    }
    
    
    
    
    
     
    public void run() {
    Node rootnode = new Node(25);
    System.out.println("Building tree with rootvalue" + rootnode.value);
    System.out.println("==");
    insert(rootnode, 11);
    insert(rootnode, 10);
    insert(rootnode, 9);
    insert(rootnode, 23);
    insert(rootnode, 79);
    System.out.println("Traversing");
    System.out.println("===");
    printInOrder(rootnode);
     
    }
    
    
     
    public void insert(Node node, int value) {
    if (value < node.value) {
    if (node.left == null) {
        System.out.println(" Inserted " + value +
    " to left of node " + node.value);
    node.left = new Node(value);
    
    } else {
    insert(node.left, value);
    }
    } else if (value > node.value) {
    if (node.right != null) {
    insert(node.right, value);
    } else {
    System.out.println(" Inserted " + value + "to right of node " + node.value);
    node.right = new Node(value);
    }
    }
    }
    
    
     
    public void printInOrder(Node node) {
    if (node != null) {
    printInOrder(node.left);
    System.out.println(" Traversed " + node.value);
    printInOrder(node.right);
    }
    }
    
    
    }

Okay the point was to understand the binary tree implementation in java. I have taken the above code from a site. I don't understand the recursive insertion method. How is it getting to the sub trees.

Can you please help me in this?

Thanks!!

[Taywin]

Err... You need to read be more familiar with Java... By the way, the code is not correct. In line 14, the "right" variable must be initialized as "null" as well.

OK, please "read" the comment below...

public void insert(Node node, int value) {
  // This is a characteristic of a binary tree - node on the left child and its
  // children are always less than the parent node.
  // Also, node on the right child and its children are always greater than the
  // parent node.

  // This characteristic applies to a tree that does not consist of duplicated value.
  // If duplicated value is allowed, it depends on how you build the tree (insert).

  // When value is less than the current node value, it means that the value
  // will be inserted to the left of the binary tree.
  if (value < node.value) {
    // If the left node has no node, assign the node to the left node
    if (node.left == null) {
      System.out.println(" Inserted " + value + " to left of node " + node.value);
    node.left = new Node(value);
    }
    // Otherwise, attempt to insert on the left node's children -> recursive call
    else {
      insert(node.left, value);
    }
  }

  // When value is greater than the current node value, it means that the value
  // will be inserted to the right of the binary tree.
  else if (value > node.value) {
    // If attempt to insert on the right node's children -> recursive call
    // Stupid code format because it could cause confusion... Not uniform...
    if (node.right != null) {
      insert(node.right, value);
    }
    // Otherwise, the right node has no node, assign the node to the right node
    else {
      System.out.println(" Inserted " + value + "to right of node " + node.value);
      node.right = new Node(value);
    }
  }
}

Note: The code ignores any node value which is equal to any existing node in the binary tree!

[ARaza110]

yes this is the thing that is bothering me, In line 18,19 and 20, it calls the recursive method insert(node.left,value), it again goes to line 12, now here (how does it get the very first value on the node.left, since the current node.left value was the previous one not the very first one).

I hope you understand what i am trying to say here.

Thanks!!

[Taywin]

OK, let's take a look how the tree is built from the code you gave. You will see why you need to initialize "right" to be null as well.

Node rootnode = new Node(25);  // assign root
    insert(rootnode, 11);
    insert(rootnode, 10);
    insert(rootnode, 9);
    insert(rootnode, 23);
    insert(rootnode, 79);

/*
Start with root is 25
           25
        /      \
      null    null    <--- look here, left & right must be initialized as null

Now inserting 11
  call insert() for the first time for insertion
    passing in the root node which has node value 25
    and the inserting value is 11
  compare the inserting value with the incoming node value => 11 < 25 ?
  it is less than, so the inserting value will be on the left side of the node
  check if the left child of the incoming node is null => node.left==null
  it is, so create a new node with the inserting value, and place it to the left
               25
            /      \
           11     null
         /    \
       null  null

Now inserting 10
  call insert() for the first time for insertion
    passing in the root node which has node value 25
    and the inserting value is 10
  compare the inserting value with the incoming node value => 10 < 25 ?
  it is less than, so the inserting value will be on the left side of the node
  check if the left child of the incoming node is null => node.left==null
  no, it is not so need to do the recursive call
    call insert() for the second time for insertion
      passing in the left child of the current node which has node value 11
      and the inserting value is 10
    compare the inserting value with the incoming node value => 10 < 11 ?
    it is less than, so the inserting value will be on the left side of the node
    check if the left child of the incoming node is null => node.left==null
    it is, so create a new node with the inserting value, and place it to the left
               25
            /      \
           11     null
         /    \
       10    null
      /  \
    null null

Now inserting 9
  call insert() for the first time for insertion
    passing in the root node which has node value 25
    and the inserting value is 9
  compare the inserting value with the incoming node value => 9 < 25 ?
  it is less than, so the inserting value will be on the left side of the node
  check if the left child of the incoming node is null => node.left==null
  no, it is not so need to do the recursive call
    call insert() for the second time for insertion
      passing in the left child of the current node which has node value 11
      and the inserting value is 9
    compare the inserting value with the incoming node value => 9 < 11 ?
    it is less than, so the inserting value will be on the left side of the node
    check if the left child of the incoming node is null => node.left==null
    no, it is not so need to do the recursive call
      call insert() for the third time for insertion
        passing in the left child of the current node which has node value 10
        and the inserting value is 9
      compare the inserting value with the incoming node value => 9 < 10 ?
      it is less than, so the inserting value will be on the left side of the node
      check if the left child of the incoming node is null => node.left==null
      it is, so create a new node with the inserting value, and place it to the left
               25
            /      \
           11     null
         /    \
       10    null
      /  \
     9   null
   /   \
 null null

Now inserting 23
  call insert() for the first time for insertion
    passing in the root node which has node value 25
    and the inserting value is 23
  compare the inserting value with the incoming node value => 23 < 25 ?
  it is less than, so the inserting value will be on the left side of the node
  check if the left child of the incoming node is null => node.left==null
  no, it is not so need to do the recursive call
    call insert() for the second time for insertion
      passing in the left child of the current node which has node value 11
      and the inserting value is 23
    compare the inserting value with the incoming node value => 23 < 11 ?
    no it is greater than, so the inserting value will be on the right side of the node
    check if the right child of the incoming node is null => node.right==null
    it is, so create a new node with the inserting value, and place it to the right
                  25
              /        \
           11         null
         /    \
       10       23
      /  \     /  \
     9  null null null
   /   \
 null null

Now inserting 79
  call insert() for the first time for insertion
    passing in the root node which has node value 25
    and the inserting value is 79
  compare the inserting value with the incoming node value => 79 < 25 ?
  no it is greater than, so the inserting value will be on the right side of the node
  check if the right child of the incoming node is null => node.right==null
  it is, so create a new node with the inserting value, and place it to the right
                  25
              /        \
           11          79
         /    \      /    \
       10       23  null null
      /  \     /  \
     9  null null null
   /   \
 null null
*/

Look at the built tree above, you will see that it maintain its characteristic of binary search tree as I said in my earlier post. If you look at each node and its lower subtree nodes, you will see that value of nodes in the left subtree of each node is always less than the node itself, and the same applies to the right subtree. Hope this would help you understand better.

[ARaza110]

Very well explained. Thank you very much for the explanation. Helped me a lot. THanks!!