amazon set 1

 

Question 1: There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).

code

  // pre-order traversal
        void assignValue( TreeNode root, int[N][N] a, ArrayList<Integer> al )
        {
            if( root == null )
        {
            return;   
        }
        for( Integer i : al )
        {
            a[i][root.data] = 1;
        }

        // add the current root to the root store array
        al.add( root.data );

        // clone it for its children
        ArrayList<Interger> cloned1 = al.clone();
        ArrayList<Interger> cloned2 = al.clone();

        if( root.left )
        {
            assignValue( root.left, a, cloned1 );
        }
        if( root.right )
        {
            assignValue( root.right, a, cloned2 );
        }

        }

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s