How can I recursively insert the Fibonacci sequence into a binary tree
-
28-04-2021 - |
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
Solution
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
OTHER TIPS
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.