int countNodes(TreeNode* root) {
     
     if (root == nullptr) {
         return 0;
     }
     
     TreeNode *left = root->left;
     TreeNode *right = root->right;
     
     int leftCount = 1;
     int rightCount = 1;
     
     while (left != nullptr) {
         leftCount++;
         
         left = left->left;
     }
     
     while (right != nullptr) {
         rightCount++;
         
         right = right->right;
     }
     
     if (leftCount == rightCount) {
         return pow(2, leftCount) - 1;    
     }
     
     return countNodes(root->left) + countNodes(root->right) + 1;
 }

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int countNodes(struct TreeNode* root) {
    if(root == NULL)
        return 0;

    int lh,rh;
    struct TreeNode *tmp;

    tmp = root->left;
    lh = 0;
    while(tmp){
        lh++;
        tmp = tmp->left;
    }

    tmp = root->right;
    rh = 0;
    while(tmp){
        rh++;
        tmp = tmp->right;
    }

    if(lh == rh)
        return (2<<lh) - 1;

    return 1 + countNodes(root->left) + countNodes(root->right);
}

//fUNCTION TO DELETE AT SPECIFIC PISTION
void deleteAtPosition(int position)
     {
     //First check if the position exsists
     //countNodes() returns the total number of nodes                      
     if(position>countNodes())
         printf("Enter valid Position");           
     else                     
         {
         //delete the first node                     
         if(position==1)
                deleteFirstNode();
         //delete last node       
         else if(position==countNodes())
                deleteLastNode();
         else
             {
             struct node *temp,*curr=head,*prev=curr;   
             /*traverse to the position and delete the node
                        prev contains all the elements before the delete position
                        curr conatins all the position after the delete position
             */
             for(int i=1;i<position;i++)
                   {
                   prev = curr;                       
                   curr = curr->next;                   
                   }       
             prev->next = NULL;
             prev->next = curr->next;                    
             }                          
         }
     }      

int countNodes(struct TreeNode* root) {
    int l=0,r=0;
    struct TreeNode* p;
    if(root==NULL){
        return 0;
    }
    
    p=root;
    while(p){
        l++;
        p=p->left;
    }
    p=root;
    while(p){
        r++;
        p=p->right;
    }
    
    if(l==r){
        return (1<<l)-1;
    }
    
    return 1+countNodes(root->left)+countNodes(root->right);
    
}

 int countNodes(TreeNode* root) {
 	// check exception
 	if (!root) {
 		return 0;
 	}
     TreeNode* l = root;
     TreeNode* r = root;
     int leftDepth = 0;
     int rightDepth = 0;
     while (l) {
     	leftDepth++;
     	l = l->left;
     }
     while (r) {
     	rightDepth++;
     	r = r->right;
     }
     if (leftDepth == rightDepth) {
     	// return (1 << leftDepth) - 1;
     	return pow(2, leftDepth) - 1;
     } else {
     	// wrong 
     	// return countNodes(l) + countNodes(r) + 1;
     	// should be 
     	return countNodes(root->left) + countNodes(root->right) + 1;
     }
 }

 int countNodes(TreeNode* root) {
     if(root==NULL){
         return 0;
     }
     
     int leftDepth=1,rightDepth=1;
     TreeNode* p=NULL;
     p=root->left;
     while(p!=NULL){
         leftDepth++;
         p=p->left;
     }
     p=root->right;
     while(p!=NULL){
         rightDepth++;
         p=p->right;
     }
     
     if(leftDepth==rightDepth){
         return (1<<leftDepth)-1;
     }else{
         return countNodes(root->left)+countNodes(root->right)+1;
     }
 
 }

 int countNodes(TreeNode* root) {
     if(!root) {
         return 0;
     }
     else {
         TreeNode* leftTree = root;
         TreeNode* rightTree = root;
         int lefth = 0;
         int righth = 0;
         while(leftTree) {
             leftTree = leftTree->left;
             lefth++;
         }
         while(rightTree) {
             rightTree = rightTree->right;
             righth++;
         }
         if(lefth == righth) {
             return (int)pow(2, lefth) - 1;
         }
         else {
             return 1 + countNodes(root->left) + countNodes(root->right);
         }
     }
 }

int countNodes(struct TreeNode* root)
{
    if( root == NULL )
        return 0;

    int heightL = 0, heightR = 0;
    struct TreeNode *p;
    p = root;
    while( p != NULL )
    {
        heightL++;
        p = p->left;
    } 

    p = root;
    while( p != NULL )
    {
        heightR++;
        p = p->right;
    }

    if( heightL == heightR )
        return (1<<heightL)-1;
    return 1 + countNodes(root->left)+countNodes(root->right);
}

 int countNodes(TreeNode* root) {
     int cnt = isCompleteTree(root);
     if (cnt != -1) return cnt;
     int leftCnt = countNodes(root->left);
     int rightCnt = countNodes(root->right);
     return leftCnt + rightCnt + 1;
 }

 int countNodes(TreeNode* root) {
     int tmp = isComplete(root);
     if (tmp != -1) return tmp;
     int l = countNodes(root->left);
     int r = countNodes(root->right);
     return 1 + l + r;
 }

/* A helper function to count nodes in a Binary Tree */
int countNodes (struct node* root) 
{ 
  if (root == NULL) 
   return 0; 
  return countNodes (root->left) + 
         countNodes (root->right) + 1; 
} 

int getIntersectionNode(struct node *head1, struct node *head2)
{
	int l1 = countNodes(head1);
	int l2 = countNodes(head2);
	int diff = abs(l1 - l2);
	return (l1 > l2)? _getIntersectionNode(diff, head1, head2):
	_getIntersectionNode(diff, head2, head1);
}

 int countNodes(TreeNode* root) {
     if (root == NULL) return 0;
     int L = 0, R = 0;
     for (TreeNode * n = root->left; n != NULL; n = n->left) ++ L;
     for (TreeNode * n = root->right; n != NULL; n = n->right) ++ R;
     if (L == R) return pow(2, L+1) - 1;
     else return 1 + countNodes(root->left) + countNodes(root->right);
 }

 int countNodes(TreeNode* root) {
     if (!root) return 0;
     int leftHeight = count(root->left);
     int rightHeight = count(root->right);
     if (leftHeight==rightHeight)
         return (1<<leftHeight)+countNodes(root->right);
     else
         return (1<<rightHeight)+countNodes(root->left);
 }

 int countNodes(TreeNode* root) {
     if(!root)
         return 0;
     vector<int> level = helper(root->left);
     if(level[0] == level[1])
         return pow(2, level[0]) + countNodes(root->right);
     else
         return pow(2, level[1]) + countNodes(root->left);
 }

QList<ListDigraph::Node> ProcessModel::topolSortReachableFrom(const QList<ListDigraph::Node>& s) {
	ListDigraph::NodeMap<bool > nodevisited(graph, false);
	QList<ListDigraph::Node> res;
	QStack<ListDigraph::Node> stack;
	ListDigraph::Node curnode;
	ListDigraph::Node pnode;
	ListDigraph::Node snode;
	QList<ListDigraph::Node> reachable = reachableFrom(s);

	// Reserve memory
	res.reserve(countNodes(graph));
	stack.reserve(countNodes(graph));

	for (int i = 0; i < s.size(); i++) {
		if (s[i] != INVALID) {
			stack.push(s[i]);
		}
	}

	bool psched;
	while (!stack.empty()) {
		curnode = stack.pop();

		if (!nodevisited[curnode]) { // This node has not been visited yet

			// Check whether all predecessors in reachable are scheduled
			psched = true;
			for (ListDigraph::InArcIt iait(graph, curnode); iait != INVALID; ++iait) {
				pnode = graph.source(iait);
				if (reachable.contains(pnode)) { // Consider only nodes which can be reached from s
					if (!nodevisited[pnode]) {
						psched = false;
						break;
					}
				}
			}

			if (psched) { // All predecessors have been visited
				res.append(curnode);
				nodevisited[curnode] = true;

				// Push the succeeding nodes
				for (ListDigraph::OutArcIt oait(graph, curnode); oait != INVALID; ++oait) {
					snode = graph.target(oait);
					if (!nodevisited[snode]) {
						stack.push(snode);
					}
				}
			} else {
				stack.prepend(curnode);
			}

		} // Else ignore the visited node
	}

	return res;
}

/**
 * method 2: using properties of bst.
 * if number of nodes in left-subtree greater than (k-1), then the k-th smallest 
 * must be in left-rubtree;
 * if number less than (k-1), then k-th node must be in right-subtree.
 * if equal, root is the one
 * Time: averag o(logn)
 */
int countNodes(struct TreeNode *root)
 {
 	int nl = 0, nr = 0;

 	if (root == NULL) return 0;
 	nl = countNodes(root->left);
 	nr = countNodes(root->right);
 	return (nl + nr + 1);
 }

int countNodes(TreeNode T) {
	int Nodes = 0;
	
	if (T != NULL) {
		Nodes++;
		Nodes += countNodes(T->Left) + countNodes(T->Right);
	}
	return Nodes;
}

 int countNodes(TreeNode* root) {
     if(!root) return 0;
     
     int l = getLeftDepth(root);
     int r = getRightDepth(root);
     
     if(l == r) return (2<<(l-1)) - 1;
     
     return countNodes(root->left) + countNodes(root->right) + 1;
 }

 int countNodes(TreeNode* root) {
     int leftHeight = 0, rightHeight = 0;
     for (TreeNode *cur = root; cur; cur = cur->left)
         ++leftHeight;
     for (TreeNode *cur = root; cur; cur = cur->right)
         ++rightHeight;
     if (leftHeight == rightHeight)
         return (1 << leftHeight) - 1;
     return countNodes(root->left) + countNodes(root->right) + 1;
 }