Fibonacci sequence binary tree console logger
One thing I would recommend is using memoization.  Make a dictionary of fibonacci numbers that you've already calculated (do the math once when the user gives you input).  When you go to calculate a node's fibonacci value, just do a check in the dictionary for the appropriate value.  This will avoid calculating the lower levels so much.
Actually, if you only know the level the node is on, you could instead put the fibonacci values in an array (python list) where the index of the array is the number that should be shown on that level of the tree.
Either way, there are ways to use memoization to avoid duplicate effort, and it can make a big difference in your speed for a lot of problems.