CODEWITHSUNDEEP
pythonsearchdictionarytreenested
AJINKYA
AJINKYA

Reputation: 801

What is the efficient way to define and traverse tree in python?

I have some products that need to be assigned categories. I have gone through some nested dictionary techniques, however just want to know the efficient way to use the tree structure.

Sample categories are as per following image, the depth shown is also the maximum depth of tree.

enter image description here

I want to take the name of elements in tree search it a string using it as substring and store in temp list if it exists.

For example: I will search for MUV, SUV, Sedan words in string if SUV exists i will store update temp =[Car, SUV]. After that traverse similarly with SUV node until the end of tree. So list at end will look similar to this [Car, SUV,Window,XYZ]

I am completely new to this data structure hence need some suggestions on defining this 4 level of tree structure and efficiently accessing it.

I am asking for efficient way because this process will be repeated at least 30000 times in program.

Upvotes: 3

Views: 746

Answers (1)

hello_there_andy
hello_there_andy

Reputation: 2083

Have a look at the ete2 python package, their trees are defined according to the Newick tree format (see wiki:Newick to gain intuition)

Defining a tree

from ete2 import Tree

t = Tree("(A,(B,(E,D)));" ) # Loads a tree structure from a newick string. The returned variable ’t’ is the root node for the tree.

print t

   /-A
--|
  |   /-B
   \-|
     |   /-E
      \-|
         \-D

Traversing a tree (more information)

for node in t.traverse("postorder"):
  # Do some analysis on node
  print node.name

A working tree-traversing Python script

Here

Related question

Algorithm to decide cut-off for collapsing this tree?

Upvotes: 2

Related Questions