CareerCup

In a binary tree there can be any value on any node, so we need to keep track of the Min. value found so far for that depth branch and propagate it until you reach the leafs, be aware not to count duplicates in the way back, a HashSet would help to avoid that,
and the final HashSet will hold all Nodes which are lesser than all their possible parents.

public static int countNumLesserNodes(Node<Integer> root) {
	if(root == null) {
		return 0;
	}
	Set<Node<Integer>> set = new HashSet<>();
	countNumLesserNodes(root.left, root.data, set);
	countNumLesserNodes(root.right, root.data, set);		
	return set.size();
}

public static void countNumLesserNodes(Node<Integer> root, int pVal, Set<Node<Integer>> set) {
	if(root == null) {
		return;
	}
	if(root.data < pVal) {
		set.add(root);
		pVal = root.data;
	}				
	countNumLesserNodes(root.left, pVal, set);
	countNumLesserNodes(root.right, pVal, set);		
}

int countNode(root) {
	if(root == null) 
		return 0;
	int cnt = 0;
	if(root.left != null && root.value > root.left.value)
		cnt += 1 + countNodes(root.left);
	if(root.right != null && root.value > root.right.value)
		cnt += 1 + countNodes(root.right);
	return cnt;

You can do this with a quick depth-first recursion.

In python:

def get_valid_nodes(root, curr_sum):
    if not root:
        return 0
    left_count = get_valid_nodes(root.left, curr_sum + root.val)
    right_count = get_valid_nodes(root.right, curr_sum + root.val)
    root_valid = 1 if root.val < curr_sum else 0
    return root_valid + left_count + right_count

What it does is keep track of the sum of values in the traversal to the current node in the tree. If it is the bottom of the tree, it returns 0. Otherwise, it recurses on its left and right child, then adds their values to 1 (if the curr node has a val less than the above sum) or 0 and returns that value.

runs in O(n log n)

class binaryProcessor{
	int count =0;
	public void countNodesLessThan(Node root) {
		countNodesLess(root.left,root.value);
		countNodesLess(root.right,root.value);
		
	}
	private void countNodesLess(Node node, int value) {
		if(node == null){
			return;
		}
		if(node.value<value){
			count++;
		}
		countNodesLess(node.left,node.value);
		countNodesLess(node.right,node.value);
	}

}

even if the root to leave path is 2->3->1 and should be 1 as last node fulfills the condition (i guess)

FindNumberOfNodes(N,max)
{
  if(N==null) return 0;
  bool isCoditionSatisfied = N<max;
  l = FindNumberOfNodes(N.Left, (isCoditionSatisfied) ? N.data : max)
  r = FindNumberOfNodes(N.Right, (isCoditionSatisfied) ? N.data : max)
  return l + r + ((isCoditionSatisfied) ? 1:0);
}

If we can modify the nodes, have a property "count" in each node indicating how many descendent nodes have values less than that node's value.

Insert: increment count property of nodes as you traverse the tree to find an appropriate insertion spot

Delete: decrement count property of nodes as you traverse the tree to find the node to delete. This is a little trickier now as you need to also update the count property of the node that will replace the deleted node when deleting a node with 2 children; this is mainly only efficient if we're dealing with a BST.

int countNodes(Node *root) {
     if(root == null || root->left==null && root->right==null) {
		return 0;
	}

	int count += countNodes(root->left);
	count +=countNodes(root->right);
   
	if(root->data > root->left->data) count++;
	if(root->data > root->right->data) count++;     
  
	return count;

}

public int countMinNodes(Node node, int min) {
        boolean flag = false;
        if (node == null) {
            return 0;
        } else {
            if (min == Integer.MIN_VALUE) {
                min = node.getValue();
            } else {
                flag = min > node.getValue();
                min = min > node.getValue() ? node.getValue() : min;
            }
            if (flag) {
                return 1 + countMinNodes(node.getlChild(), min) + countMinNodes(node.getrChild(), min);
            } else {
                return countMinNodes(node.getlChild(), min) + countMinNodes(node.getrChild(), min);
            }

        }

    }

We simply need to pass down the minimum value of all Nodes above the current Node, which is updated at each level of the stack frame. Then, return the # Nodes below you which are less than their upper Nodes, plus one if current Node is less than its upper Nodes

struct Node {
	Node* left;
	Node* right;
	int datum;
};

int getNumNodesLowerThanParents(Node* root) {
	if(!root) return 0;
	return getNumNodesLowerThanParentsHelper(root->left, root->datum) +
		  getNumNodesLowerThanParentsHelper(root->right, root->datum);
}

int getNumNodesLowerThanParentsHelper(Node* root, int minAbove) {
	if(!root) return 0;
	int thisAddition = 0;
	if(root->datum < minAbove) {
		minAbove = root->datum;
		++thisAddition;
	}
	return getNumNodesLowerThanParentsHelper(root->left, minAbove) +
		  getNumNodesLowerThanParentsHelper(root->right, minAbove) +
		  thisAddition;
}

{public int countnodes(Node node,int key)
	{
		int count=0;
		if(node!=null)
		{
			if(node.key>key)
			{
				count++;
			}
			count=count+countnodes(node.left,key);
			count = count+countnodes(node.right,key);
		}
		
		return count;
	}

}

public int countnodes(Node node,int key)
	{
		int count=0;
		if(node!=null)
		{
			if(node.key>key)
			{
				count++;
			}
			count=count+countnodes(node.left,key);
			count = count+countnodes(node.right,key);
		}
		
		return count;
	}

public int countNodesLesserThanUpperNodes(AVLTree.Node node, int maximum){
return node == null? 0 : ((node.data < maximum? 1 : 0) + countNodesLesserThanUpperNodes(node.left,Math.min(maximum, node.data) +
countNodesLesserThanUpperNodes(node.right,Math.min(maximum, node.data))));
}

public int countNodesLesserThanUpperNodes(AVLTree.Node node, int maximum){
return node == null? 0 : ((node.data < maximum? 1 : 0) + countNodesLesserThanUpperNodes(node.left,Math.min(maximum, node.data) +
countNodesLesserThanUpperNodes(node.right,Math.min(maximum, node.data))));
}