Counting Full Nodes in a Binary Tree: Iterative and Recursive Approaches

Table of Contents#

1. Binary Tree Basics
2. Recursive Approach
   • Algorithm Explanation
   • Code Implementation (Python)
   • Example Usage
3. Iterative Approach
   • Algorithm Explanation
   • Code Implementation (Python)
   • Example Usage
4. Common Practices and Best Practices
5. References

Binary Tree Basics#

A binary tree is a hierarchical data structure. Each node contains a value (or data) and pointers (references in Python) to its left and right children. Here is a simple representation of a binary tree node in Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Recursive Approach#

Algorithm Explanation#

The recursive approach to count full nodes in a binary tree is based on the principle of divide and conquer. Here's how it works:

• Base Case: If the current node is None (i.e., we have reached a leaf node or an empty subtree), we return 0 because there are no full nodes in an empty subtree.
• Recursive Case: Check if the current node has both a left and a right child. If it does, increment the count by 1. Then, recursively call the function for the left subtree and the right subtree. Finally, return the sum of the counts from the left, right subtrees, and the current node (if it's a full node).

Code Implementation (Python)#

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def count_full_nodes_recursive(root):
    if root is None:
        return 0
    count = 0
    if root.left and root.right:
        count = 1
    return count + count_full_nodes_recursive(root.left) + count_full_nodes_recursive(root.right)

Example Usage#

Let's create a sample binary tree and test our function:

# Create a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
 
print(count_full_nodes_recursive(root))

In this example, the nodes 2 (has left and right children 4 and 5) and 1 (has left and right children 2 and 3) are full nodes. So the output will be 2.

Iterative Approach#

Algorithm Explanation#

The iterative approach uses a queue (or a stack, but queue is more commonly used for level - order traversal - like operations on trees). Here's the step - by - step process:

• Initialize a queue and add the root node to it (if the root is not None).
• Initialize a count variable to 0.
• While the queue is not empty:
  • Dequeue a node from the queue.
  • Check if the dequeued node has both a left and a right child. If it does, increment the count.
  • Enqueue the left and right children (if they exist) of the dequeued node.

Code Implementation (Python)#

from collections import deque
 
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def count_full_nodes_iterative(root):
    if root is None:
        return 0
    queue = deque()
    queue.append(root)
    count = 0
    while queue:
        node = queue.popleft()
        if node.left and node.right:
            count += 1
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return count

Example Usage#

Using the same sample binary tree as above:

# Create a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
 
print(count_full_nodes_iterative(root))

The output will also be 2 as expected.

Common Practices and Best Practices#

Common Practices#

• Tree Representation: Use a class - based representation (like the TreeNode class in Python) for binary tree nodes. This makes it easy to manage node values and children.
• Traversal: For the iterative approach, using a queue for level - order traversal - like operations is a common practice. It allows us to visit each node in a systematic way.

Best Practices#

• Error Handling: Always check if the root node is None at the beginning of both recursive and iterative functions. This prevents errors when dealing with empty trees.
• Code Readability: Use descriptive variable names (like count, root, queue). In the recursive function, the base case should be clearly defined. In the iterative function, the queue operations (enqueue and dequeue) should be easy to follow.

References#

• "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. This book provides in - depth coverage of data structures and algorithms, including binary trees.
• Online resources like GeeksforGeeks (https://www.geeksforgeeks.org/) which have numerous examples and explanations of tree - related algorithms.