When given an undirected graph G represented by an adjacency list how can you use a DFS to see if that graph is a perfect binary tree?
I have been able to identify edge cases: such as using the fact that for a depth D you need 2^n-1 nodes you can can work out the max depth using a logarithm and if that isn't whole you know you don't have a perfect tree but I cant think of an efficient way of using the adjacency list and DFS to test.
CodePudding user response:
In a perfect binary tree that is not empty, with