# try to build Recursive data structures on python

184 views

### try to build Recursive data structures on python

Hey guys I have a mission on my course that I need to build a function that given a tree (tree) is represented as a tuple returns a new tree (show of Tree)

``````class Tree(object):
def __init__(self, value, nodes=None):
self.value = value
self.nodes = nodes

def __repr__(self):
if self.nodes:
return 'Tree({0},{1})'.format(self.value, repr(self.nodes))
return 'Tree({0})'.format(self.value)

def BuildTree(tree):
if type(tree) != tuple:
return Tree(tree)
<3 >
return Tree("here i need to put the height" ,list(map(BuildTree, tree)))

t1 = BuildTree((((1, 2), 3), (4, (5, 6))))
print(t1)
``````

and until now I get only like this.

Tree([Tree([Tree([Tree(1), Tree(2)]), Tree(3)]), Tree([Tree(4), Tree([Tree(5), Tree(6)])])])

But I don't know I calculate the height of each internal node I have this pic that describes the construction of the new tree. So the numbers in green are the height and the numbers in red are values I have inside the tuple

so the correct output of the new Tree is like that.

Tree(3,[Tree(2,[Tree(1,[Tree(1), Tree(2)]), Tree(3)]), Tree(2,[Tree(4), Tree(1,[Tree(5), Tree(6)])])]) by (71.8m points)

Let's describe `height` in plain words -

1. the height of the empty tree is `0`
2. the height of the non-empty tree is `1` plus the max height of the children nodes

We can write this using mathematical induction

1. if the input tree, `t` is empty, return the empty result
2. (induction) `t` is not empty. add 1 to the `max` of solved sub-problems, `t.nodes`, and return
``````def height (t):
if not t:
return 0                                    # (1)
else:
return 1 + max(height(n) for n in t.nodes)  # (2)
``````

For this to work however, you need to initialize `nodes=[]` instead of `nodes=None`. Otherwise it complicates your program a bit more -

1. if the input tree, `t` is empty, return the empty result
2. (induction) `t` is not empty. if `t.nodes` is empty, a leaf node has been reached; return 1
3. (induction) `t` is not empty and `t.nodes` is not empty. add 1 to the `max` of solved sub-problems, `t.nodes`, and return
``````def height (t):
if not t:
return 0                                   # (1)
elif not t.nodes:
return 1                                   # (2)
else:
return 1 + max(height(n) for n in t.nodes) # (3)
``````