__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: EASY
Tags: Tree algorithms

Fundamentals

Data structures
Skill types: Data structures

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 = []
		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 = []
	for i in range(len(a) + 1):
		arr1.append(i)
	stack = []

	def inorder(arr, node):
		nonlocal stack
		if node >= len(arr):
			return
		inorder(arr, node * 2)
		stack.append(node)
		inorder(arr, node * 2 + 1)
	inorder(arr1, 1)
	result = [0 for row in range(len(a))]
	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):
	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):
		top_position = int(2 ** (number_of_layers - 1)) - 1
	else:
		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:
		lheight = height(node.left)
		rheight = height(node.right)
		if lheight > rheight:
			return lheight + 1
		else:
			return rheight + 1


def floor(num: int):
	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