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)

That it doesnt need extra memory. Unlike my solution where every recursion level creates a new array. The arrays are values of the bottom level of the SumTree to be created. — Domco28, May 27 '17 at 02:21
Secondly, where are you getting the array from? Does it have some logical structure to how the elements are organized? Can you give an example of the array? — EyuelDK, May 27 '17 at 02:24

score 1 · Accepted Answer · answered May 27 '17 at 03:38

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

score 0 · Answer 2 · answered May 27 '17 at 06:24

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

EyuelDK · Answer 3 · 2017-05-27T13:35:10.547

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>

Building a sum tree from leaves

3 Answers3