Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to count children in a tree

Tags:

algorithm

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?

like image 869
turtle Avatar asked Apr 26 '13 11:04

turtle


People also ask

How can I find out the number of children in a tree?

Initialize the number of children as 0. For every node in the n-ary tree, check if its value is equal to x or not. If yes, then return the number of children. If the value of x is not equal to the current node then, push all the children of current node in the queue.

How many children can a tree node have?

In a binary search tree, parent nodes can have a maximum of two children. These children are called the “left child” and the “right child”.

How do you count the number of nodes in a binary tree?

Find the left and the right height of the given Tree for the current root value and if it is equal then return the value of (2height – 1) as the resultant count of nodes. Otherwise, recursively call for the function for the left and right sub-trees and return the sum of them + 1 as the resultant count of nodes.

Can a tree have more than 2 child nodes?

Every node can have multiple child nodes. The number of child nodes can vary from one node to the other.


1 Answers

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
like image 70
Sayakiss Avatar answered Sep 28 '22 00:09

Sayakiss