Trusted answers to developer questions

K,Jagadeeswar Reddy

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

- 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`

, and`search`

. - The
`set_root`

method will take the key as an argument and set the variable key equal to it. - The
`insert_left`

and`insert_right`

methods will insert a node as a left and right child, respectively. - The
`inorder`

method displays the inorder traversal. - The method search returns a node with a specified key.
- We need to define the
`count_nodes`

function, which will take a binary tree as an argument. - The recursive function
`count_nodes`

returns the number of nodes in the binary tree.

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': break

Enter 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_nodes`

is 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