How do I implement a state space tree (which is a binary tree) in python?

Question

Given (M, F) - With every step of a certain process, the tuple becomes either (M + F, F) or (M, M + F). So, starting with (1, 1), the following are possible:

The algorithm I've followed while drawing the tree is -

If not root, 
left_ child = (parent0 + parent1, parent1)

and right_child = (parent0, parent0 + parent1)

where parent0 is referring to the first element of the parent tuple and parent1 second.

I am completely unsure on how I would create a tree that would follow the above algorithm for creation of the tree after n steps given any starting values to M and F.

When I decided to search online, I got something along the lines of :

class Tree(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

root = Tree()
root.data = "root"
root.left = Tree()
root.left.data = "left"
root.right = Tree()
root.right.data = "right"

or

class Tree:
    def __init__(self, cargo, left=None, right=None):
        self.cargo = cargo
        self.left  = left
        self.right = right

    def __str__(self):
        return str(self.cargo)

tree = Tree(1, Tree(2), Tree(3))

I couldn't think of a way to use the above piece of code to build the state space tree I wanted to. That is, how do I implement a tree that automatically creates subtrees with the calculated values when the given input is (M, F) and n which is the number of steps in the process (i.e. the number of levels in the tree).

Answer 1

All you need is a Tree that holds two values instead of just one, plus some properties that automatically generate subtrees:

class SpaceTree:
    def __init__(self, M=1, F=1):
        self.M= M
        self.F= F
        self._left= None
        self._right= None

    @property
    def left(self):
        if self._left is None:
            self._left= SpaceTree(self.M+self.F, self.F)
        return self._left

    @property
    def right(self):
        if self._right is None:
            self._right= SpaceTree(self.M, self.F+self.M)
        return self._right

    def __repr__(self):
        return 'SpaceTree({}, {})'.format(self.M, self.F)

Now you can create a tree and traverse it as far as you want:

>>> SpaceTree()
SpaceTree(1, 1)
>>> SpaceTree().left
SpaceTree(2, 1)
>>> SpaceTree().left.right
SpaceTree(2, 3)