Searching any tree in Python

Question

I need to write a function in Python that takes a tree and an index and returns the subtree or leaf at that index.

I tried with loops and nested loops until I realized that the tree that had to run the tests was always the same:

tree = (((1, 2), 3), (4, (5, 6)), 7, (8, 9, 10))

which actually looks like this:

Sample tree

So all I needed to pass the tests given was this:

def tree_ref(tree, index):
    if len(index) == 1:
        print tree[index[0]]
    elif len(index) == 2:
        print tree[index[0]][index[1]]
    elif len(index) == 3:
        print tree[index[0]][index[1]][index[2]]
    else:
        return False

For example, for an index = (1, 1, 0) it should return the number 5 and it does.

However, I know this code won't work for other trees or index with more than 3 elements. How could I make it work for any given tree and index?

score 4 · Accepted Answer · answered Oct 31 '16 at 10:07

4

You should try to use recursion.

Something like below:

def tree_ref(tree, index):
    if len(index) == 1:
        print tree[index[0]]
    else:
        tree_ref(tree[index[0]], index[1:])

answered Oct 31 '16 at 10:07

Fehnryr

255
2
9

Thanks a lot, works perfectly. Should have considered recursion first, yes. – danielsto Oct 31 '16 at 10:25
@DanielSarmiento: please validate the answer if it solved your problem ;) – lolando Oct 31 '16 at 10:40

score 0 · Answer 2 · edited May 23 '17 at 11:48

Take a look at this: How can I implement a tree in Python? Are there any built in data structures in Python like in Java?

You should consider implementing your node as a class as described in the linked article. If you work with lists, you'll easily end up with exactly the problem you are struggling with now. A class based tree is not tied to a certain shape or depth and be more generic and easier to implement and search.

Hannu

score 0 · Answer 3 · answered May 19 '21 at 20:23

In my opinion the itertree package (I'm the author) provides a good solution for the problem.

First we build a tree representing the given tuple structure:

>>>from itertree import *
>>>root=iTree('root')
>>># we must use some helper tags ("sub","sub2","sub3") to fill the tree
>>>root += iTree('sub')
>>>root += iTree('sub')
>>>root += iTree('sub',data=7)
>>>root += iTree('sub')
>>>root[0] += iTree('sub2')
>>>root[0][0] += iTree('sub3', data=1)
>>>root[0][0] += iTree('sub3', data=2)
>>>root[0] += iTree('sub2', data=3)
>>>
>>>root[1] += iTree('sub2', data=4)
>>>root[1] += iTree('sub2')
>>>root[1][0] += iTree('sub3', data=5)
>>>root[1][0] += iTree('sub3', data=6)
>>>
>>>root[3] += iTree('sub2', data=8)
>>>root[3] += iTree('sub2', data=9)
>>>root[3] += iTree('sub2', data=10)

The tree content looks like this:

>>>root.render()
iTree('root')
     └──iTree('sub')
         └──iTree('sub2')
             └──iTree('sub3', data=1)
             └──iTree('sub3', data=2)
         └──iTree('sub2', data=3)
     └──iTree('sub')
         └──iTree('sub2', data=4)
             └──iTree('sub3', data=5)
             └──iTree('sub3', data=6)
         └──iTree('sub2')
     └──iTree('sub', data=7)
     └──iTree('sub')
     └──iTree('sub2', data=8)
     └──iTree('sub2', data=9)
     └──iTree('sub2', data=10)

The item access is now possible via index:

>>>print(root[0][0][0].d_get())
1
>>># or
>>>print(root.get_deep([1, 0, 1]).d_get())
6

The item itself also knows his index-path:

>>>print(root.get_deep([0,0,1]).idx_path)
[0, 0, 1]

A filtered access to the data content is possible too:

>>>item_filter=Filter.iTFilterData(data_value=iTInterval(2,5))
>>>for i in root.iter_all(item_filter):
>>>    print(i)
iTree("'sub2'", data=3, subtree=[])
iTree("'sub2'", data=4, subtree=[iTree("'sub3'", data=5, subtree=[]), iTree("'sub3'", data=6, subtree=[])])

Searching any tree in Python

3 Answers3