This repository has been archived by the owner on Aug 23, 2023. It is now read-only.
/
CountBinaryTree.cs
61 lines (51 loc) · 1.54 KB
/
CountBinaryTree.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using System.Collections.Generic;
namespace CS.Problems.DynamicProgramming.Count
{
/// <summary>
/// Problem statement below
/// http://www.geeksforgeeks.org/find-all-possible-trees-with-given-inorder-traversal/
/// </summary>
public class CountBinaryTree
{
public static int Count(int n)
{
return Count(0, n, new Dictionary<string, int>());
}
/// <summary>
/// If we draw the BTs ignoring symmetrical duplicates
/// we will see the count will be equal
/// to n'th Catalan number
/// And is same as the number of ways we can
/// parenthesize an expression
/// </summary>
/// <param name="start"></param>
/// <param name="end"></param>
/// <returns></returns>
private static int Count(int start, int end, Dictionary<string, int> cache)
{
if (start > end)
{
return 0;
}
//base case
if (start == end)
{
return 1;
}
var cacheKey = $"{start}-{end}";
if(cache.ContainsKey(cacheKey))
{
return cache[cacheKey];
}
var count = 0;
//break in to left & right
for (int i = start; i < end; i++)
{
count += Count(start, i, cache)
* Count(i + 1, end, cache);
}
cache.Add(cacheKey, count);
return count;
}
}
}