Related Tags

python
community creator

# How to count the number of nodes in a binary tree in Python

This program will create a binary tree and count the number of nodes in the tree.

## Algorithm

1. We need to create a class (Binary Tree) with instance variable keys, left and right.
2. Then we define methods set_root, insert_left, insert_right, inorder, and search.
3. The set_root method will take the key as an argument and set the variable key equal to it.
4. The insert_left and insert_right methods will insert a node as a left and right child, respectively.
5. The inorder method displays the inorder traversal.
6. The method search returns a node with a specified key.
7. We need to define the count_nodes function, which will take a binary tree as an argument.
8. The recursive function count_nodes returns the number of nodes in the binary tree.

## Code

Here is the code of a Python program to count the number of nodes in a binary tree:

Before pressing Run, you have to insert input values in the stdin tab. Aample input is given below: (just copy and paste in stdin tab):

insert 1 at root
insert 2 left of 1
insert 3 right of 1
insert 5 left of 2
insert 4 right of 2
count
quit

class BinaryTree:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None

def set_root(self, key):
self.key = key

def inorder(self):
if self.left is not None:
self.left.inorder()
print(self.key, end=' ')
if self.right is not None:
self.right.inorder()

def insert_left(self, new_node):
self.left = new_node

def insert_right(self, new_node):
self.right = new_node

def search(self, key):
if self.key == key:
return self
if self.left is not None:
temp =  self.left.search(key)
if temp is not None:
return temp
if self.right is not None:
temp =  self.right.search(key)
return temp
return None

def count_nodes(node):
if node is None:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)

btree = None
print('Menu (this assumes no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('count')
print('quit')

while True:
print('inorder traversal of binary tree: ', end='')
if btree is not None:
btree.inorder()
print()

do = input('What would you like to do? ').split()

operation = do.strip().lower()
if operation == 'insert':
data = int(do)
new_node = BinaryTree(data)
suboperation = do.strip().lower()
if suboperation == 'at':
btree = new_node
else:
position = do.strip().lower()
key = int(position)
ref_node = None
if btree is not None:
ref_node = btree.search(key)
if ref_node is None:
print('No such key.')
continue
if suboperation == 'left':
ref_node.insert_left(new_node)
elif suboperation == 'right':
ref_node.insert_right(new_node)

elif operation == 'count':
print('Number of nodes in tree: {}'.format(count_nodes(btree)))

elif operation == 'quit':
break

Enter the input below

Program Explanation:

1. A variable is created to store the binary tree.
2. The user is presented with a menu to perform operations on the tree.
3. Those corresponding methods are called to perform each operation.
4. count_nodes is called to count the number of nodes in the binary tree.

RELATED TAGS

python
community creator

CONTRIBUTOR 