Home > database >  Using graph traversal to test is a graph is a perfect binary tree
Using graph traversal to test is a graph is a perfect binary tree

Time:11-20

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

  • Related