Question

Let T be a binary tree with n positions that is realized with an array representation A, and let f() be the level numbering function of the positions of T, as given in Section 8.3.2. Give pseudocode descriptions of each of the methods root, parent, left, right, isExternal, and isRoot.

Answer 1

//Pseudo code for each methods

Lets assume Tree 'T' is global declared as an array 'A'.
and 'N' is size of Array.

//1.
    {
        int root()
        {
            return A[0];
        }
      
    }

//2.
    {
        int parent(int val)
        {
            int i;
            for(i=0;i<(N/2);i++)
            {
                if((((2*i)+1)<N)&&A[(2*i)+1]==val)
                    return A[i];
                else if((((2*i)+2)<N)&&A[(2*val)+2]==val)
                    return A[i];
            }
            cout<<"This value is not present in Tree"<<endl;
            return -1;
        }
    }
  
//3.
    {
        int left(int val)
        {
            int i;
            for(i=0;i<N;i++)
            {
                if(((2*i)+1)<N)
                {
                    if(A[i]==val)
                        return A[((2*i)+1)];
                }
            }
            cout<<"This value is not present in Tree"<<endl;
            return -1;
        }
    }

//4.
    {
        int right(int val)
        {
            int i;
            for(i=0;i<N;i++)
            {
                if(((2*i)+2)<N)
                {
                    if(A[i]==val)
                        return A[((2*i)+2)];
                }
            }
            cout<<"This value is not present in Tree"<<endl;
            return -1;
        }
    }
  
//5.
    {
        bool IsExternal(int val)
        {
            int i;
            for(i=0;i<N;i++)
            {
                if(A[i]==val)
                return true;
            }
            return false;
        }
    }
  
//6.
    {
        int IsRoot(int val)
        {
            if(A[0]==val)
            return true;
            return false;
        }
    }