How many leaves has a quadtree?

Question

Let N be the number of inner nodes in a quadtree. Why is the number of leaves equal to 1 + 3 * N? I don't understand how we need to argue.

Chinaware

Answer 1

Consider expanding a quadtree by subdividing a leaf node. That leaf node becomes an internal node (decreasing the leaf count by one), and four leaf nodes are added. If the previous number of internal nodes was N, the new number of internal nodes is N+1, and the number of leaves is 1 + 3*N - 1 + 4 = 1 + 3*(N+1). The general statement follows by induction.

Ideo

Ah, I see. With this explanation, it turns out to be trivial. Thanks! – Chinaware

beautiful use of mathematical induction. – Prosaic

Answer 2

TLDR: Number of Leaf Nodes = 3 * Number of Internal Nodes + 1

I would like to build on @Sneftel's answer.

Let L₁, L₂, L₃ refers to the number of leaf nodes when there are 1,2,3 internal nodes.

Whenever we add an internal node, there is a loss of 1 leaf node and gain of k leaf nodes (in quad k=4) from the previous value of the number of leaf nodes.

We start with the base condition L₁ = k , Just the root node k children ( k = 4 in quad tree)

For example:

L₂ = L₁ - 1 + k

L₃ = L₂ - 1 + k

Generally ,
L_n = L_n-1 -1 + k , where n is the number of internal nodes and the k is the branching factor ( k = 4 in quad tree)

Let's expand the equation

L_n = L_n-1 -1 + k

L_n = L_n-2 -1 + k -1 + k

If we keep expanding this, we will reach the base condition L₁ which we know is k

L_n = L₁ + ((-1 + k) + (-1 + k) .... n-1 times)

We know that the base condition L1 = k

L_n = k + ( -1 + k ) * (n - 1)

Now, Let's take a quad tree where k = 4

L_n = 4 + 3 (n - 1)
L_n = 4 + 3n - 3
L_n = 3n + 1

Number of Leaf nodes in quad tree = 3 * Number of Internal Nodes in quad tree + 1

Biblio

Answer 3

Here is a simple explanation

         1
      / | | \
     2  3 4  5

In the above quadtree there is only one inner node [represented by number 1] and 4 leaf nodes [2 3 4 5]

If you apply the formula, 1 + 3N where N is the number of inner node, you get the following

1 + 3 * 1 = 4 [which is equal to the number of leaf nodes in the above diagram]

Now lets more nodes to the quadtree

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

Inner nodes [N] = 1, 5

Leaf nodes = 2, 3, 4, 6, 7, 8, 9

Apply the formula 1 + 3N = 1 + 3*2 = 7, which is equal to the number of leaf nodes in the above diagram

Every time you subdivide a leaf node, inner node count increases by 1 and leaf code count increases by 3 (even though 4 leaf nodes are added, one the the earlier leaf node was subdivided to get the 4 new leaf nodes, (current_leaf_nodes - 1 + 4))

Bellabelladonna