CODEWITHSUNDEEP
algorithm
turtle
turtle

Reputation: 8073

How to count children in a tree

I have a list of numbers:

[1, 2, 3, 4, 5, 6, 7]

I'm interested in finding an algorithm that can sum the total children in this list if the list where a tree:

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

I'm looking for an algorithm that would give:

[6, 2, 2, 0, 0, 0, 0]


A = 6
B = 2
C = 2
D = 0
E = 0
F = 0
G = 0

Each node (except the leaves) has two children. The only exception is if the list if even:

                              1
                            /   \
                           2     3
                          / \   / 
                         4   5 6

I would like to avoid building a tree and then counting the number of children at each node. There must be a simple mathematical way to count the number of children from a list?

Upvotes: 8

Views: 4334

Answers (4)

kishore
kishore

Reputation: 127

Like we do in heap, children[i] = sum of children of all its child + number of child

Like for 0th element, a[0] = number of children of its left child + number of children of its right child + number of its child so a[0] = 2 + 2 + 2

for(int i=n-1;i>=0;i--) {
if(i*2+2 < n) a[i]+=a[i*2+2]+1;
if(i*2+1 < n) a[i]+=a[i*2+1]+1;
}

Upvotes: 0

Dave Challis
Dave Challis

Reputation: 3906

For the case where the tree is balanced (i.e. the number of elements in the input list is odd), this can be calculated with:

n = length of elements in input list

Then for element i in the output list:

d = depth of element in tree = floor(log2(i+1))+1

Then the number of children below that element in the tree is:

n_children = n - ((2^d)-1) / 2^(d-1)

So for your example of [1,2,3,4,5,6,7]:

n = 7

For array position 0 (i.e. node 1):

d = depth = floor(log2(1))+1 = 1
n_children = (7 - ((2^1)-1)) / 2^(1-1)
           = (7 - 1) / 2^0
           = 6 / 1
           = 6

Then for then array position 1, (i.e. node 2):

d = depth = floor(log2(2))+1 = 2
n_children = (7 - ((2^2)-1)) / 2^(2-1)
           = (7 - 3) / 2
           = 2

Carrying on with this gives [6, 2, 2, 0, 0, 0, 0] for i=0 to i=6.

Python code for this would look like:

import math

def n_children(list_size, i):
    depth = math.floor(math.log(i+1,2)) + 1
    return (list_size - ((2**depth)-1)) / 2**(depth-1)

print [n_children(7, i) for i in range(7)]

This outputs [6.0, 2.0, 2.0, 0.0, 0.0, 0.0, 0.0].

It'd need some modification to deal with even numbered input arrays though (easiest way might be to round array size up to nearest odd number, then subtract 1 from any odd numbered values of i, or similar).

Upvotes: 3

Sayalic
Sayalic

Reputation: 7650

1-indexed the array.

Then for node with index i, the left son is with the index 2*i, and right is the 2*i+1.

Then go through the array from the end, for the node now:

if index of his (left or right)son is out of bound of array, then he has no (left or right)son.

If not, then you can know the number of the children of his son(we go through the array from then end).The result = number of children of now's son + number of now's son.

For example:

[1, 2, 3, 4, 5, 6, 7]
A is the result array.
1.A=[0, 0, 0, 0, 0, 0, 0],now(now is a index) = 7(1-indexed) since 7*2>7, a[7]=0
2.A=[0, 0, 0, 0, 0, 0, 0],now = 6,since 6*2>7, a[6]=0
3.A=[0, 0, 0, 0, 0, 0, 0],now = 5,since 5*2>7, a[5]=0
4.A=[0, 0, 0, 0, 0, 0, 0],now = 4,since 4*2>7, a[4]=0
5.A=[0, 0, 2, 0, 0, 0, 0],now = 3,since 3*2<7 and 3*2+1<7, a[3]=2+a[6]+a[7]=2
6.A=[0, 2, 2, 0, 0, 0, 0],now = 2,since 2*2<7 and 2*2+1<7, a[2]=2+a[4]+a[5]=2
7.A=[6, 2, 2, 0, 0, 0, 0],now = 1,since 1*2<7 and 1*2+1<7, a[1]=2+a[2]+a[3]=6

Upvotes: 4

Lee Daniel Crocker
Lee Daniel Crocker

Reputation: 13171

Interpret the first array as a heap, in which the children of node n are at 2*n+1 and 2*n+2, then recursively travel the tree:

def children(t, n):
    if 2 * n + 1 >= t:
        return 0
    elif 2 * n + 2 >= t:
        return 1
    else:
        return 2 + children(t, 2 * n + 1) + children(t, 2 * n + 2)

size = 7
childcounts = [ children(size, i) for i in range(size) ]
print(childcounts)

This will print:

[6, 2, 2, 0, 0, 0, 0]

Upvotes: 1

Related Questions