Creating a tree from a list of [id, parent_id] objects

[Mark]

I've got the following simplified base.  Is there any way to optimize this? cython -a highlights everything in yellow.  Could the omap be switched to a C++ map? I tried and failed to get that working to test, but have read it would decrease performance.   I'm creating a tree by appending a child array to each object and any object with parent_id 0 is added to the returned array while children are added to the parent's child array.

# Input  l = [ [id, parent_id], ]

cpdef createTree(l):

  ret = []

  omap = {}

  for o in l:

    o.append([])   # Add array for children

    omap[o[0]] = o  # Store object by id so child can be added to parent

    if o[1] == 0: 

      ret.append(o)

    else:         

      omap[o[1]][2].append(o)

  return ret

To test I have:

import random

def genList(num):

  ret = []

  for x in range(num):

    p = 0

    # Half the time add as child to a random parent

    if random.randint(1,10) > 5 and x > 1:

      p = random.randint(1,x)

    ret.append( [x+1,p] )

  return ret

With setup.py

from distutils.core import setup

from Cython.Build import cythonize

setup(

  ext_modules = cythonize("*.pyx",language="c++"),

)

python3 setup.py build_ext --inplace

python3 -mtimeit -s'num=10000;import cutils; import utils; a = utils.genList(num);' 'cutils.createTree(a);'