Count Nodes in Complete Tree 🎯

Welcome to our lesson on counting nodes in a complete tree! In this tutorial, we'll learn how to efficiently count the number of nodes in a complete tree, a special type of binary tree that is fully populated at every level except possibly the last. Let's dive in!

What is a Complete Tree? 📝

A complete tree is a binary tree where all levels are completely filled except possibly the last level, and all nodes in the last level are as far left as possible.

Here's an example of a complete binary tree with 10 nodes:

       1
     /   \
    2     3
   / \   / \
  4   5 6   7
 /         \
8           9

In this tree, each level is fully filled, and the last level (8 and 9) is as far left as possible.

Counting Nodes in a Complete Tree 💡

Counting nodes in a complete tree can be done efficiently using mathematical formulas. Let's derive the formula:

A complete binary tree of height h has 2^h - 1 nodes.
For a complete tree of height h, the last level (level h) has 2^(h-1) nodes.
The first h - 1 levels together have 2^h - 2^(h-1) - 1 nodes.
Since each level (except the last one) has twice as many nodes as the previous level, we can write:

2^(h-1) + 2(2^(h-2) + ... + 2^2 + 2^1) + 1

Simplifying the above expression, we get:

2^h - 1

That's the formula for counting nodes in a complete tree! Let's see how we can implement it in code.

Code Examples 📝

Python Example

python

def count_nodes(height):
    return (2 ** height) - 1

# Example usage:
tree_height = 4  # height of the complete tree
print(f"Number of nodes in a complete tree of height {tree_height}:", count_nodes(tree_height))

Java Example

java

public static int countNodes(int height) {
    return (int)(Math.pow(2, height) - 1);
}

// Example usage:
int treeHeight = 4;  // height of the complete tree
System.out.printf("Number of nodes in a complete tree of height %d: %d%n", treeHeight, countNodes(treeHeight));

Quiz 💡

Wrapping Up ✅

In this lesson, we learned about complete trees and how to efficiently count the number of nodes in them using mathematical formulas. We also provided two working code examples in Python and Java.

Now that you understand counting nodes in complete trees, let's explore other tree data structures and algorithms. Happy coding! 👨‍💻