Given a Binary Tree, the task is to Count Number of Leaf Nodes in Binary Tree. A leaf node is defined as a node that does not have any child node, or in other words, both the left and right child nodes are NULL.
Code Flow for Count Number of Leaf Nodes in Binary Tree
-
Base case check for
nullnode:-
if (Objects.isNull(node)): Checks if thenodeisnull(i.e., it doesn't exist). -
Returns
0, as there are no leaf nodes in anullnode.
-
-
Leaf node check:
-
if (Objects.isNull(node.left) && Objects.isNull(node.right)): Checks if both the left and right children of the current node arenull. -
If this condition is true, the current node is a leaf node (i.e., it has no children).
-
Returns
1, as a leaf node counts as one.
-
-
Recursive case for non-leaf nodes:
-
If the current node is not
nulland is not a leaf (it has at least one child), the method recursively counts the leaf nodes in both the left and right subtrees. -
return countLeafNode(node.left) + countLeafNode(node.right):-
Recursively calls
countLeafNodeon the left child (node.left) and the right child (node.right). -
The results are added together, as the leaf nodes in both the left and right subtrees should be counted.
-
-
Let's see the code now
package org.wesome.dsalgo;
import lombok.Data;
import java.util.Objects;
@Data
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}
public class BinaryTree {
Node root;
/* The countLeafNode method performs a depth-first traversal, also known as preorder traversal of the binary tree, and is summing up the data values of all nodes. The countLeafNode method will recursively call itself until it reaches null leaf nodes, at which point it returns 0. */
public static int countLeafNode(Node node) {
if (Objects.isNull(node)) {
System.out.println("BinaryTree.countLeafNode node is null");
return 0;
}
if (Objects.isNull(node.left) && Objects.isNull(node.right)) {
System.out.println("BinaryTree.countLeafNode " + node.data + " is leaf node");
return 1;
}
/* add the node data to the sums of the left and right child nodes and recursively call countLeafNode for the left child node and countLeafNode for the right child node. */
return countLeafNode(node.left) + countLeafNode(node.right);
}
void insert(int data) {
System.out.println("BinarySearchTree.insert data = " + data);
root = insert(root, data);
}
Node insert(Node root, int data) {
if (Objects.isNull(root)) {
Node tempNode = new Node(data);
return tempNode;
}
if (data > root.data) {
root.right = insert(root.right, data);
} else {
root.left = insert(root.left, data);
}
return root;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
public class BinaryTreeTest {
@Test
void testEmptyTree() {
// Test for an empty tree (null root)
assertEquals(0, BinaryTree.countLeafNode(null), "Count of an empty tree should be 0");
}
@Test
void testSingleNodeTree() {
// Test for a tree with a single node
BinaryTree tree = new BinaryTree();
tree.insert(10);
assertEquals(1, BinaryTree.countLeafNode(tree.root), "Count of a single node tree should be the node's value");
}
@Test
void testBalancedBinaryTree() {
// Test for a balanced binary tree
BinaryTree tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(2);
tree.insert(7);
tree.insert(12);
tree.insert(18);
assertEquals(4, BinaryTree.countLeafNode(tree.root), "Count of balanced binary tree nodes should be correct");
}
@Test
void testUnbalancedBinaryTree() {
// Test for an unbalanced binary tree (sorted order insertion creating a right-skewed tree)
BinaryTree tree = new BinaryTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
assertEquals(1, BinaryTree.countLeafNode(tree.root), "Count of right-skewed tree nodes should be correct");
}
@Test
void testTreeWithNegativeValues() {
// Test for a tree with negative values
BinaryTree tree = new BinaryTree();
tree.insert(-5);
tree.insert(-3);
tree.insert(-2);
tree.insert(-1);
tree.insert(-7);
tree.insert(-4);
assertEquals(3, BinaryTree.countLeafNode(tree.root), "Count of tree with negative values should be correct");
}
@Test
void testLargeTree() {
// Test for a large tree with many nodes
BinaryTree tree = new BinaryTree();
for (int i = 1; i <= 1000; i++) {
tree.insert(i);
}
assertEquals(1, BinaryTree.countLeafNode(tree.root), "Count of large tree should be correct");
}
@Test
void testBalancedTree() {
Node root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(2);
root.left.right = new Node(7);
root.right.left = new Node(12);
root.right.right = new Node(18);
assertEquals(4, BinaryTree.countLeafNode(root), "Count of Balanced Tree should be correct");
}
@Test
void testRightSkewedTree() {
Node root = new Node(10);
root.right = new Node(20);
root.right.right = new Node(30);
root.right.right.right = new Node(40);
root.right.right.right.right = new Node(50);
assertEquals(1, BinaryTree.countLeafNode(root), "Count of Right Skewed should be correct");
}
}
plugins {
id("java")
id("io.freefair.lombok") version "8.13"
}
group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"
repositories {
mavenCentral()
}
dependencies {
testImplementation(platform("org.junit:junit-bom:5.10.0"))
testImplementation("org.junit.jupiter:junit-jupiter")
}
tasks.test {
useJUnitPlatform()
}Complexity Analysis
Time Complexity
-
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity
-
Space Complexity: O(h) (where
his the height of the tree, with worst case O(n))
