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

Question

I hope someone can help, I'm not a programmer, but I was interested in learning the Fibonacci sequence and the recursive tree ...

I created the Binary Tree class along with its associated TreeNode class and want to generate a binary tree of recursive calls created:

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

I would like to add it as the InsertFibonacci method of my binary tree, 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 

Did I add something from the 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 is 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 will not be the exact same binary tree; it will not satisfy the ordering invariant, which has a binary search tree. I assume that you just want to use your existing structure for convenience.