 # python: recursion: find number of leaves of binary tree

• Last Update :
• Techknowledgy :

At first glance your code for `num_leaves` should be like this:

```def num_leaves(my_tree):
count = 0
if my_tree.get_left() is None and my_tree.get_right() is None:
count += 1
if my_tree.get_left():
count += num_leaves(my_tree.get_left()) # added count +=
if my_tree.get_right():
count += num_leaves(my_tree.get_right()) # added count +=

return count```

This gives 3, as expected:

```a = BinaryTree(1)
a.insert_left(2)
a.insert_right(3)
a.insert_right(4)
a.get_right().insert_left(5)
print(num_leaves(a))```

This gives 2, as expected:

```a = BinaryTree(1)
a.insert_left(2)
a.insert_right(3)
print(num_leaves(a))```

I would recommend to keep all btree related functions inside the class. That's OOP.

```class BinaryTree:

def is_leaf(self):
return self.right is None and self.left is None

def count_leaves(self):
if self.is_leaf():
return 1
count = 0
if self.right is not None:
count += self.right.count_leaves()
if self.left is not None:
count += self.left.count_leaves()
return count```

Also, you've misused the boolean expression in num_leaves's first if statement. You didn't explicitly check to see if the left tree is None. Although what you wrote happens to work the same way, it looks to me like you didn't realize what you're doing.

```def num_leaves(my_tree):
if my_tree is None:
return 0
else:
return num_leaves(my_tree.get_left()) +
num_leaves(my_tree.get_right())```

Suggestion : 2

Last Updated : 14 Jul, 2022

1._
```getLeafCount(node)
1) If node is NULL then
return 0.
2) Else If left and right child nodes are NULL
return 1.
3) Else recursively calculate leaf count of the tree using below formula.
Leaf count of a tree = Leaf count of left subtree +
Leaf count of right subtree```

Output:

`The leaf count of binary tree is: 3`

Output:

`The leaf count of binary tree is: 3`

Suggestion : 3

To find the number of leaf nodes in a binary tree or other trees, we have to traverse each node and in the tree and check if the current node is a leaf node or not and count them one by one. ,To find the number of leaf nodes in a binary tree, we have to traverse each node and in the tree and check if the current node is a leaf node or not and count them one by one., So, to count all the leaf nodes we have to traverse each node in the tree and count all those nodes which are not having any child i.e, both the children are null. , For recursive solution we have to check each node one by one recursively as we have done in binary tree recursive traversal and count the nodes which are not having any child. Other types of traversal can also be used.

##### Example -
```  Input:
1 /
\
2 3 /
\/ \
4 5 6 7

Output: 4```
Leaf_Count(root)
```1.
if root is null then
2.
return 0
3.
if root - > left is null and root - > right is null then
4.
return 1
5.
else
6.
return Leaf_Count(root - > left) + Leaf_Count(root - > right)```
```class Node:
def __init__(self, data):
self.left = None
self.data = data
self.right = None

def leaf_count(root):
if root is None:
return 0
if root.left is None and root.right is None:
return 1
else:
return leaf_count(root.left) + leaf_count(root.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print(leaf_count(root))```
```class Node {
constructor(data) {
this.left = null;
this.data = data;
this.right = null;
}
}

function leafCount(root) {
if (!root) return 0;
if (!root.left && !root.right) return 1;
else return leafCount(root.left) + leafCount(root.right);
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
console.log(leafCount(root));```

Output

`4`
Leaf_Count(root)
```1.
if root is null then
return 0
2. queue.enqueue(root)
3. count = 0
4.
while queue is not empty
5. node = queue.dequeue()
6.
if node - > left is null and node - > right is null then
7. count = count + 1
8.
else
9.
if node - > left is not null then
10. queue.enqueue(node - > left)
11.
if node.right is not null then
12. queue.enqueue(node - > right)
13.
return count```

Suggestion : 4

If a node is null, return 0.,If the left child as well as the right child is null return 1.

```#Python program to count leaf nodes in a binary tree using recursion #class
for creating Nodes of the binary treeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None #class to count leaf nodes in a binary tree using recursionclass CountLeafNodes: #function to count leaf nodes in a binary tree using recursion def count_leaf_nodes(self, root): if root is None: return 0 #if there is no left child and no right child then it is a leaf node
if root.left == None and root.right == None: return 1
return self.count_leaf_nodes(root.left) + self.count_leaf_nodes(root.right) #driver codedef main(): #creating binary tree root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.left.left.left = Node(6) #creating object o = CountLeafNodes() print('No of nodes in the binary tree:', o.count_leaf_nodes(root)) if __name__ == '__main__': main()```

Suggestion : 5

We can easily find the number of leaf nodes present in any tree using recursion. A leaf node is a node whose left and right child are NULL. We just need to check this single condition to determine whether the node is a leaf node or a non leaf (internal) node.,We are given a tree, and we have to write a C program to find the total number of leaf nodes present in a tree using recursion. We have to create a recursive function which takes in root of the tree as input and returns count of number of leaf nodes present in a tree. ,Here is source code of the C Program to count the total number of leaf nodes present in a given tree. The program is successfully compiled and tested using Codeblocks gnu/GCC compiler on windows 10. The program output is also shown below.,/* C Program to find the number of leaf nodes in a Tree */

```If the input tree is
25
/
\
27 19 /
\/ \
17 91 13 55
then number of leaf nodes in this tree will be 4```
``` If the input tree is
1\
2\
3\
4\
5
then number of leaf nodes in this tree will be 1```
```If the input tree is
15
then number of leaf nodes in this tree will be 1```
`/* C Program to find the number of leaf nodes in a Tree */`
`#include <stdio.h>`
`#include <stdlib.h>`

Suggestion : 6

Learn Java and Programming through articles, code examples, and tutorials for developers of all levels.,How to traverse a binary tree in pre-order without using recursion? (solution),How to find the middle element of the linked list using a single pass? (solution),How to Print all leaf Nodes of a Binary tree in Ja...

```  public static void printLeaves(TreeNode node) {
// base case
if (node == null) {
return;
}

if (node.isLeaf()) {
System.out.printf("%s ", node.value);
}

printLeaves(node.left);
printLeaves(node.right);

}```

```/*
* Java Program to print all leaf nodes of binary tree
* using recursion
* input :   a
*          / \
*         b   f
*        / \  / \
*       c   e g  h
*      /          \
*     d            k
*
* output: d e g k
*/

public class Main {

public static void main(String[] args) throws Exception {

// let's create a binary tree
TreeNode d = new TreeNode("d");
TreeNode e = new TreeNode("e");
TreeNode g = new TreeNode("g");
TreeNode k = new TreeNode("k");

TreeNode c = new TreeNode("c", d, null);
TreeNode h = new TreeNode("h", k, null);

TreeNode b = new TreeNode("b", c, e);
TreeNode f = new TreeNode("f", g, h);

TreeNode root = new TreeNode("a", b, f);

// print all leaf nodes of binary tree using recursion
System.out
.println("Printing all leaf nodes of binary tree in Java (recursively)");
printLeaves(root);

}

/**
* A class to represent a node in binary tree
*/
private static class TreeNode {
String value;
TreeNode left;
TreeNode right;

TreeNode(String value) {
this.value = value;
}

TreeNode(String data, TreeNode left, TreeNode right) {
this.value = data;
this.left = left;
this.right = right;
}

boolean isLeaf() {
return left == null ? right == null : false;
}
}

/**
* Java method to print leaf nodes using recursion
*
* @param root
*
*/
public static void printLeaves(TreeNode node) {
// base case
if (node == null) {
return;
}

if (node.isLeaf()) {
System.out.printf("%s ", node.value);
}

printLeaves(node.left);
printLeaves(node.right);

}
}

Output
Printing all leaf nodes of binary tree in Java(recursively)
d e g k```

Suggestion : 7

10 Free Courses to learn Data Structure and Algorithms in Depth [courses],10 Free Data Structure and Algorithms Courses (courses),PreOrder traversal, both iterative and recursive,Free Data Structure and Algorithms Courses for Programmers (courses)

```private int countLeaves(TreeNode node) {
if (node == null)
return 0;

if (node.isLeaf()) {
return 1;
} else {
return countLeaves(node.left) + countLeaves(node.right);
}
}```