__Definition:__ According to Wikipedia, a [complete binary tree](https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees) is a binary tree _"where every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible."_

The Wikipedia page referenced above also mentions that _"Binary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete binary tree, this method wastes no space."_

Your task is to write a method (or function) that takes an array (or list, depending on language) of integers and, assuming that the array is ordered according to an _in-order_ traversal of a complete binary tree, returns an array that contains the values of the tree in breadth-first order.

__Example 1:__
Let the input array be `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`. This array contains the values of the following complete binary tree. 


```
          _ 7_
        /      \
       4        9
     /   \     / \
   2      6   8   10
  / \     /
 1   3   5
```
In this example, the input array happens to be sorted, but that is _not_ a requirement.

__Output 1:__ The output of the function shall be an array containing the values of the nodes of the binary tree read top-to-bottom, left-to-right. In this example, the returned array should be:

```[7, 4, 9, 2, 6, 8, 10, 1, 3, 5]```


__Example 2:__
Let the input array be `[1, 2, 2, 6, 7, 5]`. This array contains the values of the following complete binary tree. 


```
        6
      /   \
    2       5
   / \     /
  1   2   7
 
```
Note that an in-order traversal of this tree produces the input array.

__Output 2:__ The output of the function shall be an array containing the values of the nodes of the binary tree read top-to-bottom, left-to-right. In this example, the returned array should be:

```[6, 2, 5, 1, 2, 7]```

Difficulty: introductory

Starter code:

def complete_binary_tree(a):
	

Solutions:
def complete_binary_tree(a):
    def in_order(n=0):
        if n < len(a):
            yield from in_order(2 * n + 1)
            yield n
            yield from in_order(2 * n + 2)

    result = [None] * len(a)
    for i, x in zip(in_order(), a):
        result[i] = x
    return result

def mid(n):
    x = 1 << (n.bit_length() - 1)
    return x-1 if x//2 - 1 <= n-x else n-x//2

def complete_binary_tree(a):
    res, queue = [], [a]
    while queue:
        L = queue.pop(0)
        m = mid(len(L))
        res.append(L[m])
        if m: queue.append(L[:m])
        if m < len(L)-1: queue.append(L[m+1:])
    return res

import math

def complete_binary_tree(a):
    ret = []
    rows = [a]
    
    while len(rows):
        newrows = []
        #print(rows)
        for x in rows:
            ln = len(x)
            if ln > 1:
                pwr = int(math.log(ln+1, 2))
                complete_part_ln = 2**pwr - 1
                last_full_row_ln = 2**(pwr-1)
                free_row_ln = ln - complete_part_ln
                middle = complete_part_ln // 2 + (last_full_row_ln if free_row_ln > last_full_row_ln else free_row_ln)
                ret += [x[middle]]
                newrows += [x[:middle]] + [x[middle+1:]]
            else:
                ret += x
        rows = newrows

    return ret



def complete_binary_tree(a):
    def calculate(a, root = 1, cnt = 0, output = []):
        idx = list(range(1, len(a)+1))
        if (not output):
            output = [0] * len(a)
        
        if (root * 2 in idx):
            cnt, output = calculate(a, root = root * 2, cnt = cnt, output = output)
    
        output[root-1] = a[cnt]
        cnt += 1
    
        if (root * 2 + 1 in idx):
            cnt, output = calculate(a, root = root * 2 + 1, cnt = cnt, output = output)
        
        return cnt, output
    return calculate(a)[1]

def complete_binary_tree(a):
    arr1 = []    #기본 node들이 차례대로 있는 배열
    for i in range(len(a)+1):    #개수만큼 +1을 해줌. 0부터 시작하게 하기 위함
        arr1.append(i)
    stack = []    #inorder 순서를 나타낼 배열
    
    def inorder(arr, node):    #inorder라는 함수는 arr와 node값을 input으로 받음
        nonlocal stack    #함수 내의 함수에서 부르므로 nonlocal을 사용하여 내부수정이 밖에도 영향을 미치도록 함.
        if(node >= len(arr)):    
            return
        inorder(arr, node*2)
        stack.append(node)
        inorder(arr, node*2 + 1)
    inorder(arr1, 1)    #1부터하여 inorder 순서를 따냄. stack에 저장됨
        
    result = [0 for row in range(len(a))]    #result를 저장할 배열을 선언함.
    for i, lit in enumerate(result):
        result[i] = a[stack.index(i+1)]    #알맞는 값으로 바꿔줌
    return result      


def complete_binary_tree(a):
    l = len(a)
    ans = [-1]*(l+1)
    arr = a.copy()

    push_num(1, ans, arr)

    return ans[1:]

def push_num(idx, ans, a):
    if(idx >= len(ans) or len(a) == 0):
        return
    else:
        push_num(idx*2, ans, a)
        ans[idx] = a.pop(0)
        push_num(idx*2 + 1, ans, a)

from collections import deque
from math import log2, floor

def split_tree(a): # return head, left subtree, right subtree
    top_position = 0
    number_of_elements = len(a)
    number_of_layers = floor(log2(number_of_elements)) + 1
    top_size = 2 ** (number_of_layers - 1) - 1
    lowest_level_count = number_of_elements - top_size
    if lowest_level_count >= 2 ** (number_of_layers - 2): # left part of lowest level is full
        top_position = int(2**(number_of_layers - 1)) - 1
    else: # right part of lowest level is empty
        top_position = - (top_size - 1) // 2 - 1
    return a[top_position], a[:top_position], a[top_position + 1:]

def complete_binary_tree(a):
    res = []
    tree_queue = deque()
    tree_queue.append(a)
    while tree_queue:
        tree = tree_queue.popleft()
        if tree:
            (root, left, right) = split_tree(tree)
            res.append(root)
            tree_queue.append(left)
            tree_queue.append(right)
    return res

import math

def complete_binary_tree(a):
    if len(a) < 2: return a
    
    root = build(a)
    res = []
    getLevelOrder(root, res)
    return res

class Node:

    def __init__(self, data, left, right):

        self.left = left
        self.right = right
        self.data = data
        
    def __str__(self):
        return f"left = {self.left}, right = {self.right}, data = {self.data}"
        
def build(a):

    if len(a) == 0:
        return None
    if len(a) == 1:
        return Node(a[0], None, None)
    
    level = math.log2(len(a))
    level = math.ceil(level) + (1 if int(level) == level else 0)
    
    if len(a) >= 2 ** (level - 2) * 3 - 1:
        root = 2 ** (level - 1) - 1
    else:
        root = len(a) - 2 ** (level - 2)
    
    left = build(a[:root])
    right = build(a[root+1:])
    return Node(a[root], left, right)

def getLevelOrder(root, res): 
    h = height(root) 
    for i in range(1, h+1): 
        getGivenLevel(root, i, res) 

def getGivenLevel(root , level, res): 
    if root is None: 
        return
    if level == 1: 
        res.append(root.data)
    elif level > 1 : 
        getGivenLevel(root.left , level-1, res) 
        getGivenLevel(root.right , level-1, res)

        
def height(node): 
    if node is None: 
        return 0 
    else : 
        # Compute the height of each subtree  
        lheight = height(node.left) 
        rheight = height(node.right) 
        
        #Use the larger one 
        if lheight > rheight : 
            return lheight+1
        else: 
            return rheight+1

def floor(num: int):
    ''' 
    return num - (2**i-1)
    for max i that 2**i-1 <= num
    '''
    print(num)
    assert num >= 0
    i = 0
    while 2**i - 1 <= num:
        i += 1
    return num - 2**(i-1) + 1


def complete_binary_tree(a: list) -> list:
    a = a.copy()
    breadth_fst: list = []
    
    for i in range(floor(len(a))):
        breadth_fst.append(a.pop(i))

    while a:
        idx = -1
        while idx >= -len(a):
            breadth_fst.insert(0, a.pop(idx))
            idx -= 1

    return breadth_fst


import math

class BST:
    def __init__(self,value,left=None,right=None):
        self.value=value
        self.left=left
        self.right=right

def complete_binary_tree(arr):
    tree = bst_from_arr(arr)
    depth = math.floor(math.log(len(arr),2))
    output = []
    for i in range(depth+1):
        output += breadth_first_arr(tree,i)
    return output

def breadth_first_arr(tree, level):
    out = []
    if tree is None: return
    if level == 0:
        out.append(tree.value)
    elif level > 0:
        if tree.left: out += breadth_first_arr(tree.left , level-1)
        if tree.right: out += breadth_first_arr(tree.right , level-1)
    return out

def bst_from_arr(arr):
    if len(arr) > 1:
        root_index = get_root_index(arr)
        tree = BST(arr[root_index])
    else: return BST(arr[0])

    if len(arr[:root_index]) > 1:
        tree.left = bst_from_arr(arr[:root_index])
    if len(arr[:root_index]) == 1:
        tree.left = BST(arr[0])

    if len(arr[root_index+1:]) > 1:
        tree.right = bst_from_arr(arr[root_index+1:])
    if len(arr[root_index+1:]) == 1:
        tree.right = BST(arr[-1])
    return tree

def get_root_index(arr):
    left_subtree = 0
    levels = math.floor(math.log(len(arr),2))
    for i in range(0, levels):
        if not i == levels - 1:
            left_subtree += 2**i
        else:
            left_subtree += min(int((2**levels)/2),len(arr)-(2**(levels)-1))
    return left_subtree