Count Half Nodes 🎯

Welcome to our comprehensive guide on counting half nodes in a binary tree! Let's dive into this fascinating topic and learn together.

What are Binary Trees and Half Nodes? 📝

A binary tree is a data structure consisting of nodes, where each node has at most two children. This structure is essential in computer science for organizing data and solving problems efficiently.

Half nodes are nodes in a binary tree that do not have a left child but have a right child or are leaves (nodes without any children). These nodes are crucial when calculating various properties of a binary tree.

Counting Half Nodes 💡

Counting half nodes involves traversing the binary tree and keeping track of the half nodes encountered. There are two common methods to do this:

Recursive Approach
Iterative Approach

Recursive Approach 🎯

In a recursive approach, we define a helper function to count half nodes recursively for a given node. The function checks if the current node has a left child and if it doesn't, the node is a half node. The count of half nodes for the current node is the sum of the half nodes in the right subtree plus one (for the current node).

Here's a complete working example in Python:

python

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.key = key

def countHalfNodes(root):
    if root is None:
        return 0

    if root.left is None:
        return 1 + countHalfNodes(root.right)
    else:
        return countHalfNodes(root.right)

# Test the function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)

print(countHalfNodes(root))  # Output: 3

Iterative Approach 🎯

In an iterative approach, we use a Morris Traversal to count half nodes. Morris Traversal is a recursive algorithm for inorder traversal of a binary tree in linear space.

Here's a complete working example in Python:

python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def countHalfNodes(root):
    current = root
    half_nodes = 0

    while current is not None:
        if current.left is None:
            half_nodes += 1
            current = current.right
        else:
            temp = current.left
            while temp.right is not None and temp.right != current:
                temp = temp.right
            if temp.right is None:
                temp.right = current
                current = current.left
            else:
                half_nodes += 1
                temp.right = None
                current = current.right

    return half_nodes

# Test the function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)

print(countHalfNodes(root))  # Output: 3

Quiz 💡

Happy learning! 🚀