Given a height h, count the maximum number of balanced binary trees possible with height h. Print the result modulo 10^{9} + 7.
Note : A balanced binary tree is one in which for every node, the difference between heights of left and right subtree is not more than 1.
Example 1:
Input: h = 2
Output: 3 
Explanation: The maximum number of balanced 
binary trees possible with height 2 is 3. 
Example 2:
Input: h = 3
Output: 15
Explanation: The maximum number of balanced
binary trees possible with height 3 is 15. 
Your Task:  
You dont need to read input or print anything. Complete the function countBT() which takes h as input parameter and returns the maximum number of balanced binary trees possible with height h. 
Expected Time Complexity: O(h)
Expected Auxiliary Space: O(h)
Constraints:
1<= n <=10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Mathematics

Starter code: #User function Template for python3
class Solution:
    def countBT (self, h):
        # code here 

Solutions:
class Solution:

	def countBT(self, h):
		ans = [1] * (h + 1)
		for i in range(2, h + 1):
			ans[i] = ans[i - 1] * (ans[i - 1] + ans[i - 2] * 2) % 1000000007
		return ans[-1] % 1000000007


class Solution:

	def countBT(self, h):
		b = [0] * (h + 1)
		(b[0], b[1], b[2]) = (0, 1, 3)
		for i in range(3, h + 1):
			b[i] = 2 * b[i - 1] * b[i - 2] + b[i - 1] ** 2
			b[i] = b[i] % 1000000007
		return b[h]


class Solution:

	def countBT(self, h):
		count = [1] * (h + 1)
		mod = 10 ** 9 + 7
		count[0] = 1
		count[1] = 1
		for i in range(2, h + 1):
			count[i] = count[i - 1] * (2 * count[i - 2] % mod + count[i - 1]) % mod % mod
		return count[h]


class Solution:

	def countBT(self, h):
		stateMap = [0 for _ in range(h + 1)]
		(stateMap[0], stateMap[1]) = (1, 1)
		for i in range(2, h + 1):
			stateMap[i] = stateMap[i - 1] * (stateMap[i - 1] + 2 * stateMap[i - 2])
			stateMap[i] %= 10 ** 9 + 7
		return stateMap[h]


class Solution:

	def countBT(self, h):
		mod = pow(10, 9) + 7
		dp0 = 1
		dp1 = 1
		for i in range(2, h + 1):
			dp = (dp0 * dp1 * 2 + dp1 * dp1) % mod
			dp0 = dp1
			dp1 = dp
		return dp


class Solution:

	def countBT(self, h):
		dp = [1] * (h + 1)

		def foo(dp, h):
			if h < 2:
				return 1
			if dp[h] != 1:
				return dp[h]
			dp[h] = (2 * foo(dp, h - 2) + foo(dp, h - 1)) * foo(dp, h - 1) % 1000000007
			return dp[h]
		return foo(dp, h)


class Solution:

	def countBT(self, h):
		(a, b) = (1, 1)
		for i in range(2, h + 1):
			c = b ** 2 + 2 * a * b
			c = c % 1000000007
			(a, b) = (b, c)
		return int(c % (1000000000.0 + 7))


class Solution:

	def countBT(self, h):
		dp = [-1] * (h + 1)

		def counttree(h):
			if h <= 0:
				return 0
			if h == 1:
				return 1
			if h == 2:
				return 3
			if dp[h] != -1:
				return dp[h]
			h1 = counttree(h - 1) % 1000000007
			h2 = counttree(h - 2) % 1000000007
			dp[h] = (2 * h1 * h2 + h1 * h1) % 1000000007
			return dp[h]
		return counttree(h)


mod = 1000000007

class Solution:

	def countBT(self, h):
		dp = [0] * (h + 1)
		(dp[0], dp[1]) = (1, 1)
		for i in range(2, h + 1):
			dp[i] = dp[i - 1] * (2 * dp[i - 2] % mod + dp[i - 1]) % mod % mod
		return dp[h]


class Solution:

	def countBT(self, h):
		MOD = 10 ** 9 + 7
		if h == 0 or h == 1:
			return 1
		dp = [0] * (h + 1)
		(dp[0], dp[1]) = (1, 1)
		for i in range(2, h + 1):
			dp[i] = dp[i - 1] * (2 * dp[i - 2] % MOD + dp[i - 1]) % MOD % MOD
		return dp[h]


class Solution:

	def solve(self, h, dp):
		if h == 0 or h == 1:
			return 1
		if dp[h] != -1:
			return dp[h]
		total = self.solve(h - 1, dp) * self.solve(h - 2, dp) + self.solve(h - 2, dp) * self.solve(h - 1, dp) + self.solve(h - 1, dp) * self.solve(h - 1, dp)
		dp[h] = total % 1000000007
		return dp[h]

	def countBT(self, h):
		dp = [-1 for i in range(h + 1)]
		return self.solve(h, dp)


class Solution:

	def countBT(self, h):
		if h < 2:
			return 1
		mod = 1000000007
		dp1 = dp2 = 1
		for i in range(2, h + 1):
			dp3 = dp2 * (2 * dp1 + dp2) % mod
			dp1 = dp2
			dp2 = dp3
		return dp2


class Solution:

	def countBT(self, h):

		def countbt(h):
			MOD = 1000000007
			dp = [0 for i in range(h + 1)]
			dp[0] = 1
			dp[1] = 1
			for i in range(2, h + 1):
				dp[i] = dp[i - 1] * (2 * dp[i - 2] % MOD + dp[i - 1]) % MOD % MOD
			return dp[h]
		return countbt(h)


class Solution:

	def countBT(self, h):
		if h == 0 or h == 1:
			return 1
		mod = int(1000000000.0 + 7)
		dp = [0] * (h + 1)
		(dp[0], dp[1]) = (1, 1)
		for i in range(2, h + 1):
			dp[i] = dp[i - 1] * (2 * dp[i - 2] + dp[i - 1]) % mod
		return dp[h]


class Solution:

	def countBT(self, h):
		(a, b, c) = (1, 1, 3)
		if h < 2:
			return 1
		for i in range(h - 1):
			c = (b * b + 2 * a * b) % (10 ** 9 + 7)
			a = b
			b = c
		return c % (10 ** 9 + 7)


class Solution:

	def countBT(s, h):
		if h < 2:
			return 1
		dp = [1] * (h + 1)
		for i in range(2, h + 1):
			dp[i] = dp[i - 1] * (dp[i - 1] + 2 * dp[i - 2]) % (10 ** 9 + 7)
		return dp[h]


class Solution:

	def countBT(self, height):
		mod = 10 ** 9 + 7
		(a, b) = (1, 1)
		for i in range(2, height + 1):
			temp = (2 * a * b % mod + a * a % mod) % mod
			(a, b) = (temp, a)
		return a


class Solution:

	def countBT(self, height):
		mod = 1000000007
		(a, b) = (1, 1)
		for i in range(2, height + 1):
			temp = (2 * a * b % mod + a * a % mod) % mod
			(a, b) = (temp, a)
		return a


def countBTUtil(h):
	if h == 1:
		return 1
	if h == 2:
		return 3
	if h in countBTUtil.mem:
		return countBTUtil.mem[h]
	countBTUtil.mem[h] = countBTUtil(h - 1) * (countBTUtil(h - 2) * 2 + countBTUtil(h - 1)) % (10 ** 9 + 7)
	return countBTUtil.mem[h]

class Solution:

	def countBT(self, h):
		countBTUtil.mem = {}
		return countBTUtil(h)


mod = 10 ** 9 + 7

def solve(h, dp):
	if h == 0:
		return 1
	if h < 0:
		return 0
	if dp[h] != -1:
		return dp[h]
	dp[h] = solve(h - 1, dp) * (2 * solve(h - 2, dp) + solve(h - 1, dp)) % mod
	return dp[h]

class Solution:

	def countBT(self, h):
		top = right = left = 0
		dp = [-1 for _ in range(h + 1)]
		return solve(h, dp)


class Solution:

	def countBT(self, height):
		mod = 1000000007
		dp = [None for h in range(height + 1)]
		dp[0] = 1
		for i in range(1, height + 1):
			(a, b) = (0, 0)
			if i - 1 >= 0:
				a = dp[i - 1]
			if i - 2 >= 0:
				b = dp[i - 2]
			dp[i] = (2 * a * b % mod + a * a % mod) % mod
		return dp[height]


import sys
sys.setrecursionlimit(10000)

class Solution:

	def __count_bbt_helper(self, height):
		if height == 0:
			return 1
		if self.dp[height] == None:
			self.dp[height] = 0
			(a, b) = (0, 0)
			if height - 1 >= 0:
				a = self.__count_bbt_helper(height - 1)
			if height - 2 >= 0:
				b = self.__count_bbt_helper(height - 2)
			self.dp[height] = (2 * a * b % self.mod + a * a % self.mod) % self.mod
		return self.dp[height]

	def countBT(self, height):
		self.mod = 1000000007
		self.dp = [None for h in range(height + 1)]
		return self.__count_bbt_helper(height)


class Solution:

	def solve(self, h, dp):
		if h == 0:
			return 1
		if h == 1:
			return 1
		if dp[h] != -1:
			return dp[h]
		a = self.solve(h - 1, dp)
		b = self.solve(h - 2, dp)
		dp[h] = (2 * (a * b) + a * a) % (10 ** 9 + 7)
		return dp[h]

	def tabular(self, h):
		dp = [0 for i in range(h + 1)]
		dp[0] = dp[1] = 1
		for i in range(2, h + 1):
			a = dp[i - 1]
			b = dp[i - 2]
			dp[i] = (2 * (a * b) + a * a) % (10 ** 9 + 7)
		return dp[h]

	def tabularNew(self, h):
		a = b = 1
		ans = 0
		for i in range(2, h + 1):
			ans = (2 * (a * b) + a * a) % (10 ** 9 + 7)
			b = a
			a = ans
		return ans

	def countBT(self, h):
		return self.tabularNew(h)
		dp = [-1 for i in range(h + 1)]
		return self.solve(h, dp)


class Solution:

	def countBT(self, h):
		dp = [0] * h
		dp[0] = 1
		dp[1] = 3
		for i in range(2, h):
			dp[i] = (2 * (dp[i - 1] * dp[i - 2]) + dp[i - 1] ** 2) % (10 ** 9 + 7)
		return dp[-1]


class Solution:

	def countBT(self, h):
		mod = 10 ** 9 + 7
		dp = [1 for _ in range(h + 1)]
		for i in range(2, h + 1):
			dp[i] = (2 * dp[i - 1] * dp[i - 2] + dp[i - 1] * dp[i - 1]) % mod
		return dp[h]


class Solution:

	def solve(i, j, dp):
		if i == 0 or j == 0:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		count = 0
		if abs(i - j) <= 1:
			count = 1 + Solution.solve(i - 1, j, dp) + Solution.solve(i, j - 1, dp) + Solution.solve(i - 1, j - 1, dp)
		dp[i][j] = count
		return dp[i][j]

	def countBT(self, h):
		r = l = h
		dp = [0 for _ in range(h + 1)]
		mod = 1000000007
		dp[0] = 1
		dp[1] = 1
		for i in range(2, h + 1):
			dp[i] = dp[i - 1] * (2 * dp[i - 2] % mod + dp[i - 1] % mod) % mod
		return dp[h]


from collections import defaultdict
P = 10 ** 9 + 7

class Solution:

	def countBT(self, h):
		hmap = defaultdict(int)
		hmap[0] = 1
		hmap[1] = 1
		for i in range(2, h + 1):
			hmap[i] = hmap[i - 1] * hmap[i - 1] % P
			hmap[i] += 2 * (hmap[i - 1] * hmap[i - 2]) % P % P
			hmap[i] %= P
		return hmap[h]


class Solution:

	def countBT(self, h):
		t = [0 for i in range(10002)]
		MOD = 1000000007
		t[0] = 1
		t[1] = 1
		for i in range(2, h + 1):
			t[i] = t[i - 1] * (2 * t[i - 2] % MOD + t[i - 1]) % MOD % MOD
		return t[h]


class Solution:

	def countBT(self, h):
		H = [0 for i in range(h + 1)]
		H[0] = 1
		H[1] = 1
		for i in range(2, h + 1):
			H[i] = H[i - 1] * H[i - 1] + 2 * H[i - 1] * H[i - 2]
			H[i] = H[i] % 1000000007
		return H[h] % 1000000007


class Solution:

	def countBT(self, h):
		return self.solveTabu(h)

	def solveTabu(self, h):
		(prev1, prev2) = (1, 1)
		for i in range(2, h + 1):
			ans = prev1 * (2 * prev2 + prev1) % (10 ** 9 + 7)
			prev2 = prev1
			prev1 = ans
		return prev1

	def solveMem(self, n, dp):
		if n in [0, 1]:
			return 1
		if dp[n] != -1:
			return dp[n]
		a = self.solveMem(n - 1, dp)
		b = self.solveMem(n - 2, dp)
		dp[n] = a * (2 * b + a) % (10 ** 9 + 7)
		return dp[n]


class Solution:

	def countBT(self, h):
		dp = [-1] * (h + 1)
		return self.solveMem(h, dp)

	def solveMem(self, n, dp):
		if n in [0, 1]:
			return 1
		if dp[n] != -1:
			return dp[n]
		a = self.solveMem(n - 1, dp)
		b = self.solveMem(n - 2, dp)
		dp[n] = a * (2 * b + a) % (10 ** 9 + 7)
		return dp[n]


class Solution:

	def countBT(self, h):
		if h < 2:
			return 1
		dp0 = 1
		dp1 = 1
		dp2 = 3
		mod = 1000000007
		for i in range(2, h + 1):
			dp2 = int((dp1 * dp1 + 2 * dp1 * dp0) % mod)
			dp0 = dp1
			dp1 = dp2
		return dp2


class Solution:

	def countBT(self, h):
		m = 1000000007
		prev = p_prev = curr = 1
		for i in range(2, h + 1):
			curr = (prev * prev % m + 2 * prev * p_prev % m) % m
			p_prev = prev % m
			prev = curr % m
		return curr


dp = {}

class Solution:

	def countBT(self, h):
		if h == 0 or h == 1:
			return 1
		if h not in dp:
			dp[h] = int((self.countBT(h - 1) * self.countBT(h - 1) + 2 * self.countBT(h - 2) * self.countBT(h - 1)) % 1000000007)
		return dp[h]


class Solution:

	def countBT(self, n):
		if h < 2:
			return 1
		dp0 = 1
		dp1 = 1
		dp2 = 3
		MOD = 1000000007
		for i in range(2, n + 1):
			dp2 = dp1 * (2 * dp0 + dp1) % MOD
			dp0 = dp1
			dp1 = dp2
		return dp2


class Solution:

	def countBT(self, h):
		arr = [1, 3]
		for i in range(h):
			arr.append(((arr[-1] + arr[-2]) ** 2 - arr[-2] ** 2) % (10 ** 9 + 7))
		return arr[h - 1]


class Solution:

	def countBT(self, h):
		if h == 0 or h == 1:
			return 1
		mod = 1000000000.0
		dp = [0] * (h + 1)
		dp[0] = 1
		dp[1] = 1
		dp[2] = 3
		for i in range(3, h + 1):
			dp[i] = (dp[i - 1] ** 2 + 2 * dp[i - 1] * dp[i - 2]) % 1000000007
		return dp[h] % 1000000007


class Solution:

	def countBT(self, h):
		if h > 2:
			t = [0] * h
			(t[0], t[1]) = (1, 3)
			for i in range(2, h):
				t[i] = t[i - 1] * (t[i - 1] + 2 * t[i - 2]) % 1000000007
			if t[h - 1] > 10000000000.0 + 7:
				return int(t[h - 1])
			else:
				return t[h - 1]
		elif h == 2:
			return 3
		elif h == 1:
			return 1


class Solution:

	def countBT(self, h):
		if h == 2:
			return 3
		dp = [-1] * (h + 1)
		dp[0] = 1
		dp[1] = 1
		dp[2] = 3
		dp[3] = 15
		mod = 10 ** 9 + 7
		for i in range(4, h + 1):
			dp[i] = dp[i - 1] * (2 * dp[i - 2] % mod + dp[i - 1] % mod) % mod % mod
		return dp[h]


class Solution:

	def __init__(self):
		self.d = {}

	def countBT(self, h):
		if h == 0 or h == 1:
			return 1
		if h in self.d.keys():
			return self.d[h]
		x = self.countBT(h - 1) * self.countBT(h - 1) + 2 * self.countBT(h - 1) * self.countBT(h - 2)
		self.d[h] = x % (10 ** 9 + 7)
		return self.d[h]


class Solution:

	def countBT(self, h):
		dp = [0 for i in range(h + 1)]
		dp[1] = 1
		dp[2] = 3
		for i in range(3, h + 1):
			dp[i] = (dp[i - 1] * dp[i - 1] + 2 * dp[i - 1] * dp[i - 2]) % int(1000000000.0 + 7)
		return dp[h] % int(1000000000.0 + 7)


class Solution:

	def countBT(self, h):
		ans_list = []
		ans_list.append(1)
		for i in range(1, h):
			if i == 1:
				ans_list.append(3)
			else:
				temp = ans_list[-1] + ans_list[-2]
				temp = temp ** 2 - ans_list[-2] ** 2
				if temp > 10 ** 9 + 7:
					temp = temp % (10 ** 9 + 7)
				ans_list.append(temp)
		return ans_list[-1]


class Solution:
	mod = 1000000007
	dp = [0] * 1001
	dp[1] = 1
	dp[2] = 3

	def countBT(self, h):
		if self.dp[h] > 0:
			return self.dp[h]
		self.dp[h] = (self.countBT(h - 1) + self.countBT(h - 2)) ** 2 - self.countBT(h - 2) ** 2
		self.dp[h] %= self.mod
		return self.dp[h]


class Solution:

	def countBT(self, h):
		BIG_PRIME = 1000000007
		if h < 2:
			return 1
		dp0 = dp1 = 1
		dp2 = 3
		for _ in range(2, h + 1):
			dp2 = (dp1 * dp1 + 2 * dp1 * dp0) % BIG_PRIME
			dp0 = dp1
			dp1 = dp2
		return dp2


class Solution:

	def countBT(self, h):
		mod = 10 ** 9 + 7
		bbt = [1] * (h + 1)
		bbt[2] = 3
		for i in range(3, h + 1):
			x = bbt[i - 1]
			y = bbt[i - 2]
			bbt[i] = (x * y * 2 % mod + x * x % mod) % mod
		return int(bbt[h])


class Solution:

	def countBT(self, h):
		if h < 2:
			return 1
		mod = 10 ** 9 + 7
		dp0 = 1
		dp1 = 1
		dp2 = 3
		for i in range(2, h + 1):
			dp2 = dp1 * (dp1 + 2 * dp0) % mod
			dp0 = dp1
			dp1 = dp2
		return dp2