Trusted answers to developer questions
How to count the number of nodes in a binary tree in Python
K,Jagadeeswar Reddy
This program will create a binary tree and count the number of nodes in the tree.
Algorithm
- We need to create a class (
Binary Tree) with instance variable keys, left and right. - Then we define methods
set_root,insert_left,insert_right,inorder, andsearch. - The
set_rootmethod will take the key as an argument and set the variable key equal to it. - The
insert_leftandinsert_rightmethods will insert a node as a left and right child, respectively. - The
inordermethod displays the inorder traversal. - The method search returns a node with a specified key.
- We need to define the
count_nodesfunction, which will take a binary tree as an argument. - The recursive function
count_nodesreturns 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[0].strip().lower()
if operation == 'insert':
data = int(do[1])
new_node = BinaryTree(data)
suboperation = do[2].strip().lower()
if suboperation == 'at':
btree = new_node
else:
position = do[4].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':
breakEnter the input below
Program Explanation:
- A variable is created to store the binary tree.
- The user is presented with a menu to perform operations on the tree.
- Those corresponding methods are called to perform each operation.
count_nodesis called to count the number of nodes in the binary tree.
RELATED TAGS
python
community creator
CONTRIBUTOR
K,Jagadeeswar Reddy
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
