Hey All,

[thick coyote]

It looks like you are recursion to check if every subtree is valid. I haven't ran your code so I'll assume it works but if that is the case, the time complexity should be O(n) and the space complexity is O(n) as the call stack may need to hold every single node

[lucid remnant]

Would you mind explaining why it is O(n) and not O(n^2)?

My thought was O(n^2):
O(n) for visiting each node, and O(n) for traversing each subtree

[thick coyote]

Ok I could be wrong but how I understand the code, visiting the node the first time would be O(n) for every node. Then calling dfs for every sub tree would also be O(n) because it only happens to each node once. Therefore the entire time complexity would be O(2n) which simplifies to O(n)