Find Paths Going Through a Centroid that Contain the Same Number of A and B Nodes


In order to apply centroid decomposition to this problem, I need to find all paths that go through a centroid node N and have the same number of ‘(’ and ‘)’ nodes. How can I do this in O(N) time?