Count the number of leaf nodes in a binary tree

Question

I want to count the number of leaf nodes: Note. You cannot use the global / class level variable. I performed the following algorithm, and it works fine. But I want the method signature to be

countLeaves(Node node) 

I know that I can overload methods and call the argument method 2 args from 1 args, but I do not want to do this. Can anyone suggest any other method?

 int countLeaves(Node node,int count){ if(node==null) return 0; if(node.left==null && node.right==null){ return 1+count; }else{ int lc = countLeaves(node.left, count); int total = countLeaves(node.right, lc); return total; } } 

Answer 1

 int countLeaves(Node node){ if( node == null ) return 0; if( node.left == null && node.right == null ) { return 1; } else { return countLeaves(node.left) + countLeaves(node.right); } } 

You do the same thing as before, but instead of holding the current account when we go, we just say that we return the result of the sum on the left and right node. They, in turn, decide until they get into the basic frames.

Answer 2

You do not need to pass count down the call stack, only from:

 int countLeaves(Node node) { if(node==null) { return 0; } if(node.left==null && node.right==null) { return 1; } return countLeaves(node.left) + countLeaves(node.right); } 

Answer 3

We can apply two approaches: one is recursive, the other is iterative (implementation based on a queue). Here I will talk about both methods.

Recursive solution

 int count_leaf(Node node) { if(node==NULL) return 0; if(node->left==NULL && node->right==NULL) return 1; return count_leaf(node->left)+count_leaf(node->right); } 

The second method is iterative (Queue-based implementation), the idea is taken from the tree level bypass.

 int count_leaf(Node root) { int count=0; if(root==NULL) return 0; queue<Node *> myqueue; myqueue.push(root); while(!myqueue.empty()) { Node temp; temp=myqueue.top(); //Take the front element of queue myqueue.pop(); //remove the front element of queue if(temp->left==NULL && temp->right==NULL) count++; if(temp->left) myqueue.push(temp->left); if(temp->right) myqueue.push(temp->right); } return count; } 

I hope these solutions help you.

Answer 4

Fill out ??? part yourself.

 int countLeaves(Node node){ if (node==null) return 0; if (node.left==null && node.right==null){ return 1; } else { int lc = countLeaves(node.left); int rc = countLeaves(node.right); return ???; } } 

Answer 5

Since I'm still testing this implementation, no promises without errors. If there are special problems with the implementation, I am happy to receive feedback.

At first, I get positive results:

 #region CountNode utility private int CountNode(Node node, Direction d) { Func<Direction, Node> leaf = (dir) => { return dir == Direction.Left ? node.Left : node.Right; }; var done = leaf(d) == null; var root = node; var stack = new Stack<Node>( ); var count = 0; while(!done) { if (node != null) { stack.Push(node); node = leaf(d); } else { if(stack.Count > 0) { node = stack.Pop( ); // back to root, time to quit if(node == root) { done = true; continue; } // count nodes when popped ++count; // flip direction var flip = d == Direction.Left ? Direction.Right : Direction.Left; // get the leaf node node = leaf(flip); } else { done = true; } } } return count; } #endregion 

Using:

 var actLeftCount = CountNode(root, Direction.Left); var actRightCount = CountNode(root, Direction.Right); 

This has a particular advantage when counting only nodes on Left . I can pass any node to the method and get statistics for it.

Answer 6

Same as in the first comment.

  int getLeafNodeCount(Node<T> node) { if(node == null) { return 0; } if (node.leftChild == null && node.rightChild == null) { return 1; } else { return getLeafNodeCount(node.leftChild) + getLeafNodeCount(node.rightChild); } } 

Answer 7

 public int getLeafsCount(BSTNode<T> node, int count) { if(node == null || node.getData() == null){ return count; } else if(isLeaf(node)){ return ++count; }else{ int leafsLeft = getLeafsCount((BSTNode<T>) node.getLeft(), count); int leafsCount = getLeafsCount((BSTNode<T>) node.getRight(), leafsLeft); return leafsCount; } }