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

Problem: Check Whether a Binary Tree Is a Fibonacci Tree (O(h))

Given the root root of a binary tree, define a Fibonacci Tree (Fib Tree) as follows:

• For every non-null node node:
  • If node is a leaf, it satisfies the property.
  • If node has both a left child L and a right child R, then it must hold that:
    • node.val = L.val + R.val
    • and both subtrees rooted at L and R are Fibonacci Trees.
• If a node has exactly one child, the tree is not a Fibonacci Tree.

Implement a function that determines whether the tree is a Fibonacci Tree, with the constraint:

• Required time complexity is O(h) where h is the height of the tree (not the number of nodes).

Note: The interview emphasized that n refers to the tree height h, so you must avoid traversing the entire tree.

Input format (for testing here)

The tree is given as a level-order array, where null denotes a missing node.

Output format

Print true or false.

Constraints

• 0 <= number of nodes <= 2 * 10^5
• -10^9 <= node.val <= 10^9
• Tree height h can be up to 2 * 10^5

Examples

• Input: [3,1,2]
• Output: true

• Input: [3,1,null]
• Output: false

• Input: [5,2,2,1,1,1,1]
• Output: true

• Input: [4,1,2]
• Output: false

• Input: []
• Output: true