Fibonacci Meets Huffman Coding: Building and Visualising Optimal Prefix Trees in Python

If you have ever studied algorithms, you have probably seen both the Fibonacci sequence and Huffman coding. At first glance, they seem unrelated:

• Fibonacci is a number sequence that appears in math, nature, and dynamic programming.
• Huffman coding is a compression algorithm used to build efficient binary encodings.

But combining them creates a surprisingly interesting exercise. In this post, we will:

• Review the Fibonacci sequence in a beginner-friendly way.
• Review Huffman coding and how Huffman trees are built.
• Implement Fibonacci in Python. (recursive and iterative)
• Use Fibonacci numbers as frequencies (weights) for Huffman coding.
• Build a Huffman tree from those weights.
• Visualise the first 20 Fibonacci numbers as a tree and save it as an image.

This is a great mini project if you want to practice algorithmic thinking, data structures, and Python visualisation in one place.

 

Fibonacci Meets Huffman Coding

Understanding the Fibonacci Sequence

What is the Fibonacci sequence? The Fibonacci sequence is a series of numbers where each number is the sum of the previous two.

A common definition starts like this:

• F(0) = 0
• F(1) = 1

Then for n >= 2:

• F(n) = F(n – 1) + F(n – 2)

Common examples

Here are the first few Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Let us check a few steps:

• 2 = 1 + 1
• 3 = 2 + 1
• 5 = 3 + 2
• 8 = 5 + 3

Why does it matter?

Fibonacci numbers appear in many places:

• Algorithm teaching: recursion, memoisation, dynamic programming
• Math: recurrence relations, closed forms, growth behaviour
• Nature (approximate patterns): spirals in plants, branching, and seed arrangements
• Computer science: examples in performance analysis, Fibonacci heaps (advanced topic)

It is one of the most common sequences used to introduce how simple rules can create rich structure.

 

Understanding Huffman Coding and Huffman Trees

What is Huffman coding? Huffman coding is a lossless compression technique.

The key idea is simple:

• Symbols that appear more often get shorter binary codes.
• Symbols that appear less often get longer binary codes.

This reduces the total number of bits needed to represent data.

Why is it used? Huffman coding is useful because it builds an efficient encoding when you know symbol frequencies. It is used in compression-related systems and is an important concept in:

• data compression.
• prefix codes.
• greedy algorithms.
• trees and heaps.

What is a Huffman tree? A Huffman tree is a binary tree where:

• Each leaf represents a symbol
• each leaf has a frequency (weight)
• The path from root to leaf determines the symbol’s binary code:
  • left edge = 0
  • right edge = 1 (or vice versa)

Why is it a prefix tree? Huffman codes are prefix-free, which means:

• No valid code is the prefix of another valid code.

That makes decoding unambiguous. As soon as a complete code is matched, you know exactly which symbol it represents.

How does Huffman build an optimal prefix tree? Huffman coding uses a greedy algorithm:

• Start with all symbols as separate nodes. (with frequencies)
• Repeatedly take the two nodes with the smallest frequencies.
• Merge them into a new internal node whose weight is the sum of their weights.
• Put the merged node back into the pool.
• Continue until only one node remains. (the root)

This process produces an optimal prefix tree for the given frequencies, meaning it minimises the weighted average code length.

 

Python Fibonacci Implementations (Recursive and Iterative)

Before we build a Huffman tree, we need Fibonacci numbers. We will implement Fibonacci in two ways:

• Recursive. (easy to understand, slower without memoisation)
• Iterative. (fast and practical)

 

Recursive Fibonacci Function

Step-by-step idea

The recursive version follows the mathematical definition directly:

• If n is 0, return 0
• If n is 1, return 1
• otherwise return fib(n-1) + fib(n-2)

This is elegant, but it repeats the same subproblems many times.

def fib_recursive(n: int) -> int:
   """
   Return the nth Fibonacci number using plain recursion.

   Warning:
      This implementation is simple but inefficient for larger n
      because it recomputes many values.
   """

   if n < 0:
      raise ValueError("n must be >= 0")

   # Base cases
   if n == 0:
      return 0
   if n == 1:
      return 1

   # Recursive step
   return fib_recursive(n - 1) + fib_recursive(n - 2)


# Example usage
if __name__ == "__main__":
   for i in range(10):
      print(f"fib_recursive({i}) = {fib_recursive(i)}")

 

 

Iterative (Non-Recursive) Fibonacci Function

Step-by-step idea

The iterative version keeps track of the last two values and updates them in a loop. This avoids recursive calls and is much faster for typical use.

def fib_iterative(n: int) -> int:
   """
   Return the nth Fibonacci number using iteration.

   This is efficient and suitable for practical use.
   """
   if n < 0:
      raise ValueError("n must be >= 0")

   # Base cases
   if n == 0:
      return 0
   if n == 1:
      return 1

   a, b = 0, 1 # a = F(0), b = F(1)

   # Compute up to F(n)
   for _ in range(2, n + 1):
      a, b = b, a + b

   return b


# Example usage
if __name__ == "__main__":
   for i in range(10):
      print(f"fib_iterative({i}) = {fib_iterative(i)}")

 

Iterative (Non-Recursive) Fibonacci Function

Step-by-step idea

The iterative version keeps track of the last two values and updates them in a loop. This avoids recursive calls and is much faster for typical use.

def fib_iterative(n: int) -> int:
   """
   Return the nth Fibonacci number using iteration.

   This is efficient and suitable for practical use.
   """
   if n < 0:
      raise ValueError("n must be >= 0")

   # Base cases
   if n == 0:
      return 0
   if n == 1:
      return 1

   a, b = 0, 1 # a = F(0), b = F(1)

   # Compute up to F(n)
   for _ in range(2, n + 1):
      a, b = b, a + b

   return b


# Example usage
if __name__ == "__main__":
   for i in range(10):
      print(f"fib_iterative({i}) = {fib_iterative(i)}")

 

Using Fibonacci Numbers as Huffman Frequencies

Now for the interesting part. We will:

• Generate Fibonacci numbers.
• Use them as weights. (frequencies)
• Build a Huffman tree from those weights.
• Extract Huffman codes.

To keep Huffman coding meaningful, each Fibonacci number will represent the frequency of a symbol such as S1, S2, …, S20.

Important practical note about zeros

Huffman coding usually expects positive frequencies for active symbols. If we start the Fibonacci sequence with F(0)=0, then the first term is 0. We can still include it as a weight in some experiments, but for a normal Huffman tree, it is more practical to start from F(1) or filter out zeros. In the code below, we will generate terms and skip zero-frequency values before building the tree.

 

Step 1: Generate Fibonacci numbers (list form)

This helper function returns the first n Fibonacci terms.

def fibonacci_sequence(n: int, start_index: int = 0) -> list[int]:
   """
   Generate n Fibonacci numbers starting at F(start_index).

   Example:
   fibonacci_sequence(5, start_index=0) -> [0, 1, 1, 2, 3]
   fibonacci_sequence(5, start_index=1) -> [1, 1, 2, 3, 5]
   """
   if n <= 0:
      return []
   if start_index < 0:
      raise ValueError("start_index must be >= 0")

   # Build enough Fibonacci values iteratively up to the needed index
   max_index = start_index + n - 1
   fibs = [0, 1]

   # Handle small cases
   if max_index == 0:
      fibs = [0]
   else:
      while len(fibs) <= max_index:
         fibs.append(fibs[-1] + fibs[-2])

   return fibs[start_index:start_index + n]


# Example usage
if __name__ == "__main__":
   print("First 10 Fibonacci numbers from F(0):", fibonacci_sequence(10, start_index=0))
   print("First 10 Fibonacci numbers from F(1):", fibonacci_sequence(10, start_index=1))

 

Step 2: Build a Huffman tree using Fibonacci weights

Step-by-step idea

We will implement Huffman coding using Python’s heapq (a priority queue).

Process:

• Create one node per symbol with its Fibonacci weight.
• Push all nodes into a min-heap.
• Pop the two smallest.
• Merge them into a parent node.
• Push the parent back.
• Repeat until one root remains.

Then we will traverse the tree to generate binary codes.

 

import heapq
import itertools
from dataclasses import dataclass
from typing import Optional


@dataclass
class HuffmanNode:
    """
    Node in a Huffman tree.
    """
    weight: int
    symbol: Optional[str] = None   # Leaf nodes have a symbol, internal nodes do not
    left: Optional["HuffmanNode"] = None
    right: Optional["HuffmanNode"] = None

    def is_leaf(self) -> bool:
        return self.left is None and self.right is None


def build_huffman_tree(symbol_weights: dict[str, int]) -> HuffmanNode:
    """
    Build a Huffman tree from a mapping of symbol -> weight.

    Returns:
        Root HuffmanNode

    Notes:
        - Symbols with weight <= 0 are ignored. - If only one valid symbol exists, a single-node tree is returned. """ # Filter out non-positive weights (common practical choice) filtered = {s: w for s, w in symbol_weights.items() if w > 0}
    if not filtered:
        raise ValueError("At least one symbol must have a positive weight")

    # A tie-break counter avoids comparing HuffmanNode instances directly
    counter = itertools.count()

    # Min-heap items are tuples: (weight, tie_break_id, node)
    heap = []
    for symbol, weight in filtered.items():
        node = HuffmanNode(weight=weight, symbol=symbol)
        heapq.heappush(heap, (weight, next(counter), node))

    # Special case: one symbol only
    if len(heap) == 1:
        return heap[0][2]

    # Greedy merge process
    while len(heap) > 1:
        w1, _, n1 = heapq.heappop(heap)
        w2, _, n2 = heapq.heappop(heap)

        parent = HuffmanNode(
            weight=w1 + w2,
            symbol=None,
            left=n1,
            right=n2
        )
        heapq.heappush(heap, (parent.weight, next(counter), parent))

    return heap[0][2]


def generate_huffman_codes(root: HuffmanNode) -> dict[str, str]:
    """
    Traverse the Huffman tree to generate prefix codes.

    Convention:
        left edge = '0'
        right edge = '1'
    """
    codes: dict[str, str] = {}

    # Handle single-node tree
    if root.is_leaf() and root.symbol is not None:
        codes[root.symbol] = "0"
        return codes

    def dfs(node: HuffmanNode, prefix: str) -> None:
        if node.is_leaf():
            # Leaf must contain a symbol
            if node.symbol is not None:
                codes[node.symbol] = prefix
            return

        if node.left is not None:
            dfs(node.left, prefix + "0")
        if node.right is not None:
            dfs(node.right, prefix + "1")

    dfs(root, "")
    return codes


if __name__ == "__main__":
    # Use the first 10 Fibonacci numbers starting at F(1): 1,1,2,3,5,...
    fibs = fibonacci_sequence(10, start_index=1)

    # Map them to symbols
    symbol_weights = {f"S{i+1}": w for i, w in enumerate(fibs)}

    # Build Huffman tree and codes
    root = build_huffman_tree(symbol_weights)
    codes = generate_huffman_codes(root)

    print("Symbol weights:")
    for s, w in symbol_weights.items():
        print(f"  {s}: {w}")

    print("\nHuffman codes:")
    for s, code in sorted(codes.items()):
        print(f"  {s}: {code}")

 

Visualising the Huffman Tree (First 20 Fibonacci Numbers)

To make this more intuitive, we will visualise the Huffman tree built from the first 20 Fibonacci terms (starting at F(1) by default to avoid the zero term).

We will use:

• networkx for graph representation.
• matplotlib for plotting.

Install the required libraries

pip install networkx matplotlib

 

Step-by-step idea for visualisation

1. Generate the first 20 Fibonacci numbers.
2. Build the Huffman tree.
3. Convert the tree into a graph.
4. Compute positions for nodes in a top-down tree layout.
5. Draw the graph and save it as an image.

The code below saves the image as huffman_fibonacci_tree_20.png.

import heapq
import itertools
from dataclasses import dataclass
from typing import Optional

import matplotlib.pyplot as plt
import networkx as nx


# -------------------------------
# Fibonacci helpers
# -------------------------------

def fibonacci_sequence(n: int, start_index: int = 1) -> list[int]:
    """
    Generate n Fibonacci numbers starting at F(start_index).

    Default start_index=1 avoids the zero term for Huffman frequencies.
    """
    if n <= 0:
        return []
    if start_index < 0: raise ValueError("start_index must be >= 0")

    max_index = start_index + n - 1

    # Build Fibonacci values iteratively
    fibs = [0, 1]
    while len(fibs) <= max_index: fibs.append(fibs[-1] + fibs[-2]) return fibs[start_index:start_index + n] # ------------------------------- # Huffman tree implementation # ------------------------------- @dataclass class HuffmanNode: weight: int symbol: Optional[str] = None left: Optional["HuffmanNode"] = None right: Optional["HuffmanNode"] = None def is_leaf(self) -> bool:
        return self.left is None and self.right is None


def build_huffman_tree(symbol_weights: dict[str, int]) -> HuffmanNode:
    """
    Build a Huffman tree from symbol weights using a min-heap.
    """
    filtered = {s: w for s, w in symbol_weights.items() if w > 0}
    if not filtered:
        raise ValueError("Need at least one positive weight")

    counter = itertools.count()
    heap = []

    for symbol, weight in filtered.items():
        node = HuffmanNode(weight=weight, symbol=symbol)
        heapq.heappush(heap, (weight, next(counter), node))

    # If only one symbol, return it directly
    if len(heap) == 1:
        return heap[0][2]

    while len(heap) > 1:
        w1, _, n1 = heapq.heappop(heap)
        w2, _, n2 = heapq.heappop(heap)

        parent = HuffmanNode(weight=w1 + w2, left=n1, right=n2)
        heapq.heappush(heap, (parent.weight, next(counter), parent))

    return heap[0][2]


def generate_huffman_codes(root: HuffmanNode) -> dict[str, str]:
    """
    Generate binary Huffman codes from the tree.
    """
    codes = {}

    if root.is_leaf() and root.symbol is not None:
        return {root.symbol: "0"}

    def dfs(node: HuffmanNode, prefix: str):
        if node.is_leaf():
            if node.symbol is not None:
                codes[node.symbol] = prefix
            return

        if node.left:
            dfs(node.left, prefix + "0")
        if node.right:
            dfs(node.right, prefix + "1")

    dfs(root, "")
    return codes


# -------------------------------
# Tree to NetworkX graph
# -------------------------------

def add_huffman_tree_to_graph(root: HuffmanNode):
    """
    Convert Huffman tree to a NetworkX DiGraph.

    Returns:
        G: directed graph
        root_id: root node ID
        labels: dict of node_id -> label string
        edge_labels: dict of (parent_id, child_id) -> '0' or '1'
    """
    G = nx.DiGraph()
    labels = {}
    edge_labels = {}

    # Unique IDs for graph nodes
    id_counter = itertools.count()

    def visit(node: HuffmanNode):
        node_id = next(id_counter)

        # Label internal and leaf nodes differently
        if node.is_leaf():
            labels[node_id] = f"{node.symbol}\\n(w={node.weight})"
        else:
            labels[node_id] = f"w={node.weight}"

        G.add_node(node_id)

        if node.left is not None:
            left_id = visit(node.left)
            G.add_edge(node_id, left_id)
            edge_labels[(node_id, left_id)] = "0"

        if node.right is not None:
            right_id = visit(node.right)
            G.add_edge(node_id, right_id)
            edge_labels[(node_id, right_id)] = "1"

        return node_id

    root_id = visit(root)
    return G, root_id, labels, edge_labels


def hierarchical_tree_layout(G: nx.DiGraph, root, width=1.0, vert_gap=0.12, vert_loc=0, xcenter=0.5):
    """
    Create a hierarchical layout for a directed tree.

    This produces a top-down layout suitable for tree visualization.
    """
    pos = {}

    def _layout(node, left, right, depth):
        x = (left + right) / 2
        y = vert_loc - depth * vert_gap
        pos[node] = (x, y)

        children = list(G.successors(node))
        if not children:
            return

        # Split available horizontal space among children
        step = (right - left) / len(children)
        for i, child in enumerate(children):
            child_left = left + i * step
            child_right = left + (i + 1) * step
            _layout(child, child_left, child_right, depth + 1)

    _layout(root, 0, width, 0)
    return pos


# -------------------------------
# Main script: build + visualize
# -------------------------------

def main():
    # First 20 Fibonacci numbers from F(1): 1,1,2,3,5,...
    n_terms = 20
    fibs = fibonacci_sequence(n_terms, start_index=1)

    # Assign symbols S1..S20 to these weights
    symbol_weights = {f"S{i+1}": w for i, w in enumerate(fibs)}

    # Build Huffman tree and codes
    root = build_huffman_tree(symbol_weights)
    codes = generate_huffman_codes(root)

    # Print a summary to the console
    print("Fibonacci-based symbol weights:")
    for symbol, weight in symbol_weights.items():
        print(f"  {symbol}: {weight}")

    print("\nGenerated Huffman codes:")
    for symbol in sorted(codes):
        print(f"  {symbol}: {codes[symbol]}")

    # Convert tree to graph
    G, root_id, labels, edge_labels = add_huffman_tree_to_graph(root)
    pos = hierarchical_tree_layout(G, root_id, width=1.0, vert_gap=0.10, vert_loc=0, xcenter=0.5)

    # Draw the tree
    plt.figure(figsize=(22, 12))

    nx.draw(
        G,
        pos,
        with_labels=False,   # We will draw custom labels separately
        node_size=1600,
        arrows=False
    )

    nx.draw_networkx_labels(
        G,
        pos,
        labels=labels,
        font_size=8
    )

    nx.draw_networkx_edge_labels(
        G,
        pos,
        edge_labels=edge_labels,
        font_size=8
    )

    plt.title("Huffman Tree Built from the First 20 Fibonacci Numbers (F(1) to F(20))")
    plt.axis("off")
    plt.tight_layout()

    output_file = "huffman_fibonacci_tree_20.png"
    plt.savefig(output_file, dpi=200)
    print(f"\nSaved tree visualization to: {output_file}")

    # Optional: display the plot in a local environment
    plt.show()


if __name__ == "__main__":
    main()

You can easily customise:

• Number of terms: change n_terms = 20
• Starting index: change start_index=1 to 0 (but remember F(0)=0)
• Figure size/label font size: adjust plotting settings for larger trees

 

Recursive vs Iterative Fibonacci: Complexity and Performance

Both implementations are correct, but they behave very differently.

Recursive Fibonacci (plain recursion)

• Time complexity: approximately O(2^n) (exponential)
• Space complexity: O(n) due to call stack depth
• Pros:
  • easy to read
  • mirrors the mathematical definition
• Cons:
  • very slow for larger n
  • Repeated work explodes quickly

Iterative Fibonacci

• • Time complexity: O(n)
  • Space complexity: O(1) (constant extra space)
• Pros:
  • fast and practical
  • no recursion depth issues
• Cons:
  • slightly less “mathematical-looking” than recursion

Which one should you use here? For building Huffman trees from many Fibonacci terms, use the iterative version (or memoisation / dynamic programming). The recursive version is excellent for teaching, but not for performance.

 

Why Combining Fibonacci and Huffman Trees Is Interesting

Using Fibonacci numbers as Huffman frequencies gives us a deterministic, structured set of weights with increasing values.

That makes it useful for experimentation because:

• The input distribution is not random.
• The weights grow gradually.
• You can observe that Huffman first merges small-weighted nodes and builds deeper branches for less frequent symbols.

You also get a nice bridge between topics:

• recurrence sequences. (Fibonacci)
• greedy algorithms. (Huffman)
• data structures. (heaps and trees)
• visualisation. (graph plotting in Python)

This kind of “cross-topic” coding exercise is one of the best ways to strengthen algorithm intuition.

 

Conclusion

In this post, we combined two classic concepts in computer science and mathematics:

• Fibonacci sequence for generating structured numeric weights
• Huffman coding for building an optimal prefix tree from those weights

We covered:

• what Fibonacci numbers are and where they appear
• How Huffman coding works and why it is optimal for prefix coding
• recursive and iterative Fibonacci implementations in Python
• a full Huffman tree builder using Fibonacci weights
• a visualisation pipeline to save the Huffman tree as an image

If you want to extend this project, here are a few ideas:

• Compare Huffman trees from Fibonacci vs random weights.
• compute average code length and entropy.
• Add decoding logic for generated Huffman codes.
• try larger n and see how the tree shape changes.