Thread: recursive check if a node can be accessed by two other nodes in a Binary Tree

Originally Posted by kmdv

If you want to get the number of parents, you need a parent counter for each node, and then:

1. Reset counter for every node to 0.
2. Recursively visit nodes. For each visited node, increment its counter. If the counter reaches 1, continue visiting its children, otherwise return.

Each node will hold the number of parent nodes (assuming that there are no cycles).

Hi thanks, is it achievable with 1 function?
the code i came up with doesnt seems to go over 1 ever

Code:

bool checknode(CPPtr SP){    bool chkl = false;
    bool chkr = false;
    bool chk = false;
    if(SP==NULL){
        return false;    
    }
    else {
        


        chkl = checknode(SP->left);
        chkr = checknode(SP->right);
         
        
        SP->count++;
        


        if(SP->count>1){
            return true;        //return true if a node is called twice
        }
        


        if(chkl==true||chkr==true){
            chk = true;
        }
        }
    return chk;
    }

the code i came up with doesnt seems to go over 1 ever

How would it? You are returning a boolean value.

By the by, I don't think kmdv intended that you should make count a member of the structure. The information would need to be updated during every tree mutation or reset during your counting operation. You can just use the stack, the recursion, to process this information.

Soma

Originally Posted by phantomotap

How would it? You are returning a boolean value.

By the by, I don't think kmdv intended that you should make count a member of the structure. The information would need to be updated during every tree mutation or reset during your counting operation. You can just use the stack, the recursion, to process this information.

Soma

yah.. i meant the counter doesnt go over 1
i'll try without count in the structure

but i'm not sure i get the idea of count just being in the stack, my right sub tree may have connected to some node to my left sub tree. Very confused on how to implement this count even if the count is in the structure :S

I'm unable to increment my count after i set it to 0.

Code:

SP->count = 0;		
		if(SP->count == 0){
		cout<<SP->id<<"  "<<SP->data<<"  "<<SP->count<<endl;


			SP->count++;
		}




		if(SP->count>1){
			return true;		//return true if a node is called more than once
		}
	


		if(chkl==true||chkr==true){
			chk = true;
		}
		chkl = checknode(SP->left);
		chkr = checknode(SP->right);

problem solved! make another function to set count to 0, the other one to increment and check howmany times it has been visitied