Teaching Kids Programming – Count the Number of Nodes in Binary Tree using DFS and BFS Algorithm


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a Binary Tree, we can count the number of nodes using either Depth First Search (DFS Algorithm) and Breadth First Search (BFS Algorithm).

binary-tree Teaching Kids Programming - Count the Number of Nodes in Binary Tree using DFS and BFS Algorithm algorithms BFS DFS teaching kids programming youtube video

binary-tree

Binary Tree Definition in Python:

1
2
3
4
5
class TreeNode:
  def __init__(self, val, left = None, right = None):
     self.val = val
     self.left = left
     self.right = right
class TreeNode:
  def __init__(self, val, left = None, right = None):
     self.val = val
     self.left = left
     self.right = right

Depth First Search Algorithm to Count the Nodes in Binary Tree

The total number of nodes equal to the number of nodes in the left tree, plus the number of nodes in the right tree, plus one (current node). We can do this in Recursion.

1
2
3
4
def countNodes(root: TreeNode) -> int:
  if root is None:
    return 0
  return countNodes(root.left) + countNodes(root.right) + 1
def countNodes(root: TreeNode) -> int:
  if root is None:
    return 0
  return countNodes(root.left) + countNodes(root.right) + 1

The base case is that when the node is None – we return zero.

Breadth First Search Algorithm to Count the Nodes in Binary Tree

We can also traverse the binary tree in level-by-level, and count the number of nodes along the way.

1
2
3
4
5
6
7
8
9
10
11
12
13
def countNodes(root: TreeNode) -> int:
  if root is None:
     return 0
  q = [root]
  ans = 0
  while len(q) > 0:
     p = q.pop(0)
     ans += 1
     if not (p.left is None):
       q.append(p.left)
     if not (p.right is None):
       q.append(p.right)
  return ans
def countNodes(root: TreeNode) -> int:
  if root is None:
     return 0
  q = [root]
  ans = 0
  while len(q) > 0:
     p = q.pop(0)
     ans += 1
     if not (p.left is None):
       q.append(p.left)
     if not (p.right is None):
       q.append(p.right)
  return ans

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
418 words
Last Post: Overclocking ARM CPU of Raspberry PI 4 and 400 with Temperature Cooling Measures
Next Post: Algorithms to Check if Intervals are Self-Contained

The Permanent URL is: Teaching Kids Programming – Count the Number of Nodes in Binary Tree using DFS and BFS Algorithm

Leave a Reply