Those nodes in the tree which have only one child are known as half nodes i.e., A node is a half node if only one child node is present among left or right child nodes.

To find the number of half nodes in a binary tree, we have to traverse each node and in the tree and check if the current node is a half node or not and count them one by one.

To find the number of half nodes in a binary tree, we have to traverse each node and in the tree and check if the current node is half node or not and count them one by one.

Those nodes in the tree which have only one child (either left or right child) are known as half nodes.

A node is a half node if one of the child node is
`null`

and other one has child.

So, to count all the leaf nodes we have to traverse each node in the
tree and count all those nodes which are having only one child i.e, one
of the child will present and other one should be
`null`

.

Input: 1 / \ 2 3 / / 4 6Output: 2

We can solve this problem in two ways-

For recursive solution we have to check each node one by one recursively as we have done in binary tree recursive traversal and count the nodes which are having both the children.

__1.__ if root is null then
__2.__ return 0
__3.__ count = 0
__4.__ if (root->left is not null and root->right is null) or
(root->left is null and root->right is not null) then
__5.__ count = count + 1
__6.__ left_count = Half_Node_Count(root->left)
__7.__ right_count = Half_Node_Count(root->right)
__8.__ count = count + left_count + right_count
__9.__ return count

```
class Node:
def __init__(self, data):
self.left = None
self.data = data
self.right = None
def half_node_count(root):
if root is None:
return 0
count = 0
if (root.left and root.right is None) or (root.left is None and root.right):
count = count + 1
left_half = half_node_count(root.left)
right_half = half_node_count(root.right)
count = count + left_half + right_half
return count
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
print(half_node_count(root))
```

```
class Node {
constructor(data) {
this.left = null;
this.data = data;
this.right = null;
}
}
function halfNodeCount(root) {
if (!root) return 0;
let count = 0;
if ((root.left && !root.right) || (!root.left && root.right)) {
count++;
}
left_half = halfNodeCount(root.left);
right_half = halfNodeCount(root.right);
count = count + left_half + right_half;
return count;
}
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
console.log(halfNodeCount(root));
```

Output

1

For iterative solution, we have to traverse each node in level order and count the nodes which are not having any child.

__1.__ if root is null then return 0
__2.__ queue.enqueue(root)
__3.__ count = 0
__4.__ while queue is not empty
__5.__ node = queue.dequeue()
__6.__ if (root->left is not null and root->right is null) or
(root->left is null and root->right is not null) then
__7.__ count = count + 1
__8.__ if node->left is not null then
__9.__ queue.enqueue(node->left)
__10.__ if node.right is not null then
__11.__ queue.enqueue(node->right)
__12.__ return count

```
import queue
class Node:
def __init__(self, data):
self.left = None
self.data = data
self.right = None
def half_node_count(root):
if root is None:
return 0
q = queue.Queue()
q.put(root)
count = 0
while not q.empty():
node = q.get()
if (node.left and node.right is None) or (node.left is None and node.right):
count = count + 1
if node.left:
q.put(node.left)
if node.right:
q.put(node.right)
return count
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
print(half_node_count(root))
```

```
class Node {
constructor(data) {
this.left = null;
this.data = data;
this.right = null;
}
}
function halfNodeCount(root) {
if (!root) return 0;
const q = [];
q.push(root);
let count = 0;
while (q.length > 0) {
const node = q.shift();
if ((node.left && !node.right) || (!node.left && node.right)) {
count++;
}
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
return count;
}
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
console.log(halfNodeCount(root));
```

Output

1

**Time complexity: ** The time complexity of both of these
solution will be **O(n)** because we are just traversing each
element of node one by one.

__AUTHOR__