#!/usr/bin/python2.7
class Node:
"the basic element of a tree"
data = -1
left = None
right = None
def __init__(self, data: int):
"constructor to initiate a node"
# store data
self.data = data
# store reference (next item)
self.left = None
self.right = None
return
@classmethod
def make(self, data: [int], index : int = 0, level_size : int = 1, prev_sum: int = 0):
"constructor to initiate nodes"
if index >= len(data):
return None
# the data to be returned
ret = Node(data[index])
# note: level_size should be 2^level, so either level or level_size can be passed
# but passing a variable means you don't have to calculate it 2x, so it's a bit faster
child_index = index + level_size # the next index will be the current index + level_size
child_index += (index - prev_sum) # plus how ever far the index passed the last level's sum
# child_index = index * 2 + 1 # the expected index for the non-sparse case
current_sum = prev_sum + level_size # the total number of elements reviewed
next_level_size = level_size + level_size # the expected size of the next level
ret.left = Node.make(data, child_index, next_level_size, current_sum)
ret.right = Node.make(data, child_index+1, next_level_size, current_sum)
return ret
def __str__(self, level=0):
"allows you to call print() on a node"
ret = "-"*level+repr(self.data)+"\n"
if self.left != None:
ret += self.left.__str__(level+1)
if self.right != None:
ret += self.right.__str__(level+1)
return ret
def serialize(self) -> str:
"will turn the entire tree into a single line string"
s = ""
s += str(self.data)
if self.left != None or self.right != None:
s += " ["
if self.left != None:
s += self.left.serialize()
else:
s += "null"
s += " "
if self.right != None:
s += self.right.serialize()
else:
s += "null"
s += "]"
return s
def get_size(self) -> int:
"gets the size of the tree"
s = 1
if self.left != None:
s += self.left.get_size()
if self.right != None:
s += self.right.get_size()
return s
"""
# demonstrate the tree API works
c = Node(1)
c.left = Node(2)
c.right = Node(3)
c.left.left = Node(4)
c.left.left.left = Node(8)
c.left.left.right = Node(9)
c.left.right = Node(5)
c.left.right.left = Node(10)
c.left.right.right = Node(11)
c.right.left = Node(6)
c.right.left.left = Node(12)
c.right.left.right = Node(13)
c.right.right = Node(7)
c.right.right.left = Node(14)
c.right.right.right = Node(15)
print("The size is ", c.get_size())
print("The value is ", c.serialize())
"""
vals = list(range(1,31+1))
c = Node.make(vals)
print("The size is ", c.get_size())
print("The value is ", c.serialize())
print(c)
