CODEWITHSUNDEEP
c#
Shah
Shah

Reputation: 73

Recursive call and how object is iterating in tree

I stumble upon this piece of code as i am learning oop so it is bit confusing for me. I am implementing binary search tree and this particular function implement IN-Order traversal.

 class Binary_Tree
{
    //Nodes class Inner class.
    public class Nodes
     {

         public Nodes rightChild;
         public Nodes leftChild;
         public  int value;

         public void InOrder()
          {
             if(leftChild != null)
                {
                  leftChild.InOrder();
                }

            Console.WriteLine(this.value);
            if(rightChild != null)
               {
                 rightChild.InOrder();
               }

           }

      }

    //Member of nodes class inside Binary tree class
    private Nodes root;

    //Default Constructor
    Binary_Tree() { }

    static void Main(string [] args)
    {

        Binary_Tree b = new Binary_Tree();
        b.Insertion(18);

        b.Insertion(10);
        b.Insertion(11);
        b.Insertion(5);
        b.Insertion(6);
        b.Insertion(3);
        b.root.InOrder();
        Console.WriteLine();

    }
}

My concern is with leftChild.InOrder(); every time this function calls itself it moves from one leftChild to next leftChild. How is it possible because I think it should only move when there is an statement like leftChild = leftChild.leftChild or maybe leftChild = leftChild.next.

Thanks in advance.

Upvotes: 0

Views: 77

Answers (3)

Julián Urbano
Julián Urbano

Reputation: 8488

As you're learning Object Orientation, let's see if this helps (I know this is not strictly true as said, just mean to help a bit here).

In structured, you would do:

void InOrder(Tree node){ ... }

and then call like InOrder(leftChild). This can be understood as: function InOrder, please, run yourself with leftChild as your node argument.

With objects, you have:

class Tree{
    void InOrder(){ ... }
}

and then call like leftChild.InOrder(). This can be understood as: object leftChild, please, run your method InOrder.

So you don't need to do something like leftChild=leftChild.leftChild because you tell your objects to run their respective method, and not the method to run with different arguments. That is, the method is run several times, each time with a different node.

Note that in OO every method is enclosed within a class, which explicitly means that every (non-static) method receives an argument of that type, which is this (the object we asked to run the method).

Upvotes: 1

Phillip Ngan
Phillip Ngan

Reputation: 16106

You can rewrite the code to show 'this' explicitly.

public class Tree {

public Tree leftChild { get; set; }
public Tree rightChild { get; set; }

public object value { get; set; }   

public void InOrder()
{
    if(this.leftChild != null)
    {
        this.leftChild.InOrder();
    }

    Console.WriteLine(this.value);
    if(this.rightChild != null)
    {
        this.rightChild.InOrder();
    }
}

When you enter InOrder(), the current object is 'this'. The recursive call is made on the object 'this.leftChild', which is not the same object as 'this' (in fact it is the child object). That's how the recursion happens.

Upvotes: 1

Wiktor Zychla
Wiktor Zychla

Reputation: 48250

This is because leftChild becomes this in the called method, which in turn has its own leftChild and rightChild.

What you miss probably here is that when you call an instance method on a reference, the reference becomes this in the called method.

Upvotes: 2

Related Questions