How can I recursively insert the Fibonacci sequence into a binary tree

Question

Hope someone can help, I'm not a programmer, but have been interested in exploring Fibonacci sequence and it's recursive tree...

I've created a Binary Tree class, along with an associated TreeNode class, and want to generate a binary tree of the recursive calls created by:

f(n) = f(n-1) + f(n-2) for a given value of n

I'd want to add it as an InsertFibonacci method of my Binary Tree class, replacing the standard Insert method:

def insertNode(self, root, inputData):
    if root == None:
        return self.addNode(inputData)
    else:
        if inputData <= root.nodeData:
            root.left = self.insertNode(root.left, inputData)
        else:
            root.right = self.insertNode(root.right, inputData)
        return root

Would I add somekind of decorator to the Fib function?

# Fib function
def f(n):

    def helper(n):
        left = f(n-1)
        right = f(n-2)
        return left,right

    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        left, right = helper(n)
        return left + right

Answer 1

Here's the simplest solution I can think of:

class FibTree(object):
    def __init__(self, n):
        self.n = n
        if n < 2:
            self.value = n
        else:
            self.left = FibTree(n - 1)
            self.right = FibTree(n - 2)
            self.value = self.left.value + self.right.value

Answer 2

Here's one way:

def insertFibonacci(self, n):
    current = self.addNode(n)
    if n > 1:
        current.left = self.insertFibonacci(n-1)
        current.right = self.insertFibonacci(n-2)
        # if you want the fibonacci numbers instead of the calls:
        # current.value = current.left.value + current.right.value
    return current

Assumes positive n. Should return the root of the fibonacci call tree.

Note that this won't exactly be the same kind of binary tree; it won't satisfy the ordering invariant that a binary search tree does. I'm assuming you just want to use your existing structure for convenience.