Building a sum tree from leaves

Question

Hey i am preparing for exams and i could use some help. The task is to build a binary sum tree (parent node key is a sum of children keys) from an array of values of leaves (left to right) which is always 2^n long. I first transform the array to an array of nodes. Then i have made a recursive function that combines pairs and calls itself on a new array of created nodes. Is there a better way of doing this task? maybe one that is "in place"? e.g.

input: [1,2,3,4]

output:

      10
    /    \
   3      7
  / \    / \
 1   2  3   4

class SumTree:
    def __init__(self):
        self.root = None

class Node:
    def __init__(self):
        self.key = 0
        self.parent = None
        self.left = None
        self.right = None

def makeNode(key):
    n = Node()
    n.key = key
    return n

def buildSumTree(array):
    for i in range(len(array)):
        array[i] = makeNode(array[i])
    tree = SumTree()
    tree.root = buildSumTree_rec(array)
    return tree

def buildSumTree_rec(array):
    if len(array) == 1 :
        return array[0]
    else:       
        a = []
        for i in range(0, len(array) // 2, 2):
            n = makeNode(array[i].key + array[i + 1].key)
            n.left = array[i]
            n.right = array[i + 1]
            array[i].parent = n
            array[i + 1].parent = n
            a.append(n)
        return buildSumTree_rec(a)

Answer 1

This implementation only stores the leaves and nothing else, thus using no additional memory for storing nodes. It also does not mutate the leaves, i.e. no changes are performed, only read operations. All other information is computed on the fly. At the moment the output is basic, one line per depth.

import math

class SumTree:

  def __init__(self, leaves):
    self.leaves = leaves

  def nodeAt(self, i, j):
    if i < self.height() - 1:
      return self.nodeAt(i+1, 2*j) + self.nodeAt(i+1, 2*j+1)
    elif i == self.height() - 1:
      return self.leaves[j]
    else:
      raise 'no nodes exists at this depth.'

  def nodesAtDepth(self, i):
    return [self.nodeAt(i, j) for j in range(self.widthAtDepth(i))]

  def maxWidth(self):
    return self.widthAtDepth(self.height() - 1)

  def widthAtDepth(self, i):
    return 2 ** i

  def height(self):
    return math.floor(math.log(len(self.leaves), 2)) + 1

  def __str__(self):
    result = ''
    width = self.maxWidth()
    for i in range(self.height()):
      result += '{}\n'.format(self.nodesAtDepth(i))
    return result

tree = SumTree(list(range(1, 5)))
print('leaves', tree.leaves)
print('height', tree.height())
print(tree)

<script src="//repl.it/embed/IUUa/2.js"></script>

Answer 2

The following code builds the tree from the leaves to the root. It repeatedly connects two child nodes to their freshly created parent node until only one node remains.

class Node:
    def __init__(self, left, right):
        self.left = left
        self.right = right
        self.value = sum(n.value for n in (left, right) if n is not None)

    @classmethod
    def create_leaf(cls, value):
        leaf = cls(None, None)
        leaf.value = value
        return leaf


INPUT = [1, 2, 3, 4]

nodes = [Node.create_leaf(v) for v in INPUT]
while len(nodes) > 1:
    inodes = iter(nodes)
    nodes = [Node(*pair) for pair in zip(inodes, inodes)]

root_node = nodes[0]

Iteration by pairs is based on: Iterating over every two elements in a list

Answer 3

Typically something like this:

def buildSumTree(array):
    return buildSumTree2(array, 0, len(array))

def buildSumTree2(array, startpos, length):
    if length < 1:
        return None
    if length == 1:
        return makeNode(array[startpos])
    halflen = length/2
    l = buildSumTree2(array, startpos, halflen)
    r = buildSumTree2(array, startpos+halflen, length-halflen)
    n = makeNode(l.key + r.key)
    n.left = l
    n.right = r
    return n