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).


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

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

        // 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 );


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: Logo

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s