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 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 wordsloading...
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