CODEWITHSUNDEEP
pythonlistbinary-tree
J0ker98
J0ker98

Reputation: 457

Finding elements for each binary tree level in python

What I'm trying to do is to get each element's level.

I'm currently using this code:

re = {0: [b.keys()[0]]}
n = 1
for a in b:
    l = []
    for e in s[a]:
        l.append(e)
    if l != []:
        re.update({n: l})
    n += 1
print re

That is giving me the following output:

{"0": ["a"], "1": ["b"], "2": ["i"], "3": ["c", "d"], "4": ["f", "g", "h"], "5": ["e", "l"]}

What I'm doing wrong here?

Upvotes: 4

Views: 1698

Answers (3)

Aakash Verma
Aakash Verma

Reputation: 3994

Let's assume you have a dictionary 'd' like that.

d = {"a": ["b"], "b": ["c", "d"], "c": ["i"], "d": ["e", "l"], "e": ["f", "g", "h"], "f": [], "g": [], "h": [], "i": [], "l": []}
keys=d.keys()
keys.sort()
def getKey(l):
  for key,value in d.items():
    if l == value:
      return key

val=dict()# to store level of each node
val['a']=0
for l in keys:
  for v in d.values():
    if l in v:
     key = getKey(v)
     val[l]=int(val.get(key,0))+1
     print(l,val[l])

Upvotes: 0

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476534

There are some problems here:

  1. you use [s.keys()[0]] as a way to find the "root" of the tree. Note however that dictionaries are unordered (yes in the CPython-3.6 dictionaries use insertion order, but this is seen as an implementation detail), so there is no guarantee that [s.keys()[0]] is actually the root; and
  2. you perform a single pass over the dictionary, but again since dictionaries are unordered, it is not guaranteed that the parent will be assigned already.

Finding roots

So we need to solve the two problems. The first one can be solved by looking for nodes that are no child of another element. So we can write it as:

nonroots = {c for cs in s.values() for c in cs}

these are all nodes that are children, so that means that all keys in the dictionary that are not in children, are roots:

roots = [k for k in s if k not in nonroots]

The roots are on level 0, so we can set it to:

levels[0] = roots

Roots: The Next Generations

now for each iteration, we construct the next generation, by looking up the values corresponding to the previous iteration.

next_gen = [c for k in prev_gen for c in s.get(k,())]

So now we can turn this into a loop: we keep constructing a new generation as long as the previous generation contains at least one elemen. So a complete implementation is:

nonroots = {c for cs in s.values() for c in cs}
level = [k for k in s if k not in nonroots]
generation = 0
result = {}
while level:
    result[generation] = level
    generation += 1
    level = [c for k in level for c in s.get(k,())]

at the end, result is a dictionary that maps all levels to a list of children.

Note that we better use a list instead of a dictionary, since generations start with index 0, and we know that if there is a generation i, then there is also a generation i-1 (for i > 0). So we can turn it into a list like:

nonroots = {c for cs in s.values() for c in cs}
level = [k for k in s if k not in nonroots]
result = []
while level:
    result.append(level)
    level = [c for k in level for c in s.get(k,())]

This gives us:

>>> result
[['a'], ['b'], ['c', 'd'], ['i', 'e', 'l'], ['f', 'g', 'h']]

For given root(s)

We can also use an approach where the caller provides the root(s), in which case we thus generate a tree. We can alter the existing approach, for instance:

def get_levels(tree, roots):
    result = []
    roots = list(roots)
    while roots:
        result.append(roots)
        roots = [c for k in roots for c in tree.get(k,())]
    return result

Now we can thus call it with a given list of roots. In case the roots are not the real roots, we will get an ordering for the subtree(s) under the given tree:

>>> get_levels(s, ['a'])
[['a'], ['b'], ['c', 'd'], ['i', 'e', 'l'], ['f', 'g', 'h']]
>>> get_levels(s, ['c'])
[['c'], ['i']]
>>> get_levels(s, ['i','l'])
[['i', 'l']]
>>> get_levels(s, ['i','e'])
[['i', 'e'], ['f', 'g', 'h']]

Upvotes: 4

Ajax1234
Ajax1234

Reputation: 71451

You can use recursion:

from collections import defaultdict
listing1 = defaultdict(list)
s = {"a": ["b"], "b": ["c", "d"], "c": ["i"], "d": ["e", "l"], "e": ["f", "g", "h"], "f": [], "g": [], "h": [], "i": [], "l": []}
def get_listing(current_node, count):
    global listing1 
    listing1[count].append(current_node)
    for i in s[current_node]:
        get_listing(i, count+1)

get_listing('a', 0)
print(dict(listing1))

Output:

{0: ['a'], 1: ['b'], 2: ['c', 'd'], 3: ['i', 'e', 'l'], 4: ['f', 'g', 'h']}

Note that as pointed out in the comments by @WillemVanOnsem and @quamrana, dict.keys() will return an unsorted list, thus making {0: [s.keys()[0]]} unreliable as the root start.

Upvotes: 2

Related Questions