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?
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.
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”.
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.
Every node can have multiple child nodes. The number of child nodes can vary from one node to the other.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With