try to build Recursive data structures on python

Question

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)])])])

Answer 1

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)