Check Whether a Binary Tree Is a Fibonacci Tree in O(h) Time

Problem: Determine Whether a Binary Tree Is a Fibonacci Tree (O(h)) You receive the root root of a binary tree. Call it a Fibonacci Tree (Fib Tree) when it meets these conditions: Each non-null node must obey the following: A leaf automatically meets the requirement. When node has a left child L and a right child R, all of the following must be true: node.val equals L.val + R.val The subtrees whose roots are L and R must each be Fibonacci Trees. Any node with only one child…