Python - Flat list tree implementation: Given child, get parent?

Question

I'm creating a python class for a tree in which each node has a number of children given by "order" (but each child only has one node). I have a method, children(self,i), which returns the children of a node at index i. I need to implement parent(self, i) which will get the parent of a child at index i.

Here's what I have so far:

class Tree:
  def __init__(self, order=2, l=[]):
    self._tree = l
    self._order = order

  def children(self, i):
    left = self._tree[(i+1)*self._order-1]
    right = self._tree[(i+1)*self._order]
    return [left, right]

  def parent(self, i):
    if i>len(self._tree):
        return ValueError
    elif i==0:
        return None
    else:
        #get parent of node i

An example tree represented by order=2 and list [45, 2, 123, 1, 8, 40, 456] would look like this:

      45
    /    \
  2       123
 / \     /   \
1   8   40   456   

I know that there's probably a way I can reverse the method I used for children(self, i) but I'm not sure how.

Answer 1

You would do the inverse operation:

else:
    #get parent of node i
    return self._tree[(i-1)//self._order]

Note that your implementation is only working for binary trees (you return two children, not n). Correct it like this:

def children(self, i):
    return self._tree[(i*self._order+1):((i+1)*self._order+1)]