current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.5 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 0 down vote favorite

I want to create 2D array as below:

For Example: 

For level 3:


         7            => Array[2]

   3          6       => Array[1]

1     2     4     5   => Array[0]


i.e. Array = [[1,2,4,5], [3,6], [7]]

.

For level 4:

                    15                          => Array[3]

         7                      14              => Array[2]

   3          6           10           13       => Array[1]

1     2     4     5    8     9     11     12    => Array[0]


i.e. Array = [[1,2,4,5,8,9,11,12], [3,6,10,13], [7,14], [15]]

What I need is a function taking number of level as argument returning Array as mentioned above.

i.e:

def function(level):
    ''' ..........................


    ...........................'''
    return Array
share|improve this question
    
i think the question is a bit unclear, I didnt understand what you mean by associating an 2D array to a Binary Tree – Daniel yesterday
    
Hello, I'm sorry. The rule for filling array is like perfect binary tree, So, I think its easy to understand. – Ezer Neupane Rames yesterday
1  
Let us see you really tried something yourself. – dmitryro yesterday
    
Thank You all... :) – Ezer Neupane Rames 21 hours ago
up vote 0 down vote accepted

Your data structure is recursive, so it's natural to use a recursive function to produce it.

The root node of the tree of depth depth is n = 2 ** depth - 1; it's more efficient to calculate that using bit shifting. The left subtree has a root node of n // 2, the right subtree is identical except that n // 2 is added to all its nodes.

Here's a recursive generator that produces the desired list.

def btree(depth):
    if depth < 1:
        return

    n = (1 << depth) - 1
    yield [n]

    a = n // 2
    for seq in btree(depth - 1):
        yield seq + [u + a for u in seq]

lst = list(btree(4))[::-1]
print(lst)

output

[[1, 2, 4, 5, 8, 9, 11, 12], [3, 6, 10, 13], [7, 14], [15]]

If you want to print the tree rows in top-down order, you can just do this:

for row in btree(5):
    print(row)

output

[31]
[15, 30]
[7, 14, 22, 29]
[3, 6, 10, 13, 18, 21, 25, 28]
[1, 2, 4, 5, 8, 9, 11, 12, 16, 17, 19, 20, 23, 24, 26, 27]
share|improve this answer
    
Thank you very much. That is exactly what I want. – Ezer Neupane Rames 21 hours ago
    
@EzerNeupaneRames If my answer has helped you, please consider accepting it. – PM 2Ring 21 hours ago
    
ohh... Yeah, I didn't know about that. Thank You again for the information. – Ezer Neupane Rames 20 hours ago
up vote 0 down vote

Hint: Here is the last row of numbers

def last_row(level):
    m = 2 ** (level - 1)
    L = [0 for i in range(m)]
    L[0] = 1
    k = 1
    while k < m:
        incr = 2 * k - 1
        for i in range(k):
            L[k+i] = L[i] + incr
        k = incr + 1
    return L
share|improve this answer
up vote 0 down vote

Here is another recursive solution that I figured. The left sub-tree value is floor(current value) and the right sub-tree value is (current value -1). I pre-calculate the necessary powers of 2, but the draw-back is my passing of additional arguments (lists): In any case, hopefully this will be helpful for clarity when building a solution.

def driver(level):
    if level <= 0:
        return None
    # initialize the list to have (level) columns
    lst = [[] for i in range(level)]
    # pre-calculate the necessary powers of 2
    powers = [1]
    for i in range(1, level+1):
        powers.append(powers[i-1] << 1)

    # call the main calculation function
    calc(level, powers[level]-1, lst, powers)

    return lst

def calc(level, val, lst, powers):
    # add the value in pre-order
    lst[level-1].append(val)
    # base case, level is 1,
    # do not make additional recursive calls here
    if level > 1:
        # calculate values in the left sub-tree
        calc(level-1, val - powers[level-1], lst, powers)
        # calculate values in the right sub-tree
        calc(level-1, val-1, lst, powers)

print(driver(4))
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.