Using graph traversal to test is a graph is a perfect binary tree

user_9766517 0
Viewed 97

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.

binary-tree graph-algorithm algorithm
2 Answers

In a perfect binary tree that is not empty, with nodes, we have these properties:

  • The number of nodes is one less than a power of 2, i.e. ℎ=log2(+1) is integer. =2ℎ−1
  • The number of edges is −1
  • There are no nodes with more than 3 neighbors.
  • When > 1, there is (only) one node with exactly 2 neighbors: it is the root.
  • When > 1, the leaves of the tree have only one neighbor: there are 2ℎ-1 of them.
  • The distance between the root and any leaf is ℎ−1.

These properties can be checked one after the other. Once you have identified the root, you can perform a traversal to check the distance property. Either with DFS or BFS.

user_54598390

If the graph is empty, or has only one vertex, then return true.

Otherwise, check to make sure the graph is connected and acyclic.

Then, if it's a perfect binary tree, there must be only one vertex of degree 2. That's the root. Let a and b be its two children. Then:

let depthA = depthIfPerfect(a, root);
let depthB = depthIfPerfect(b, root);
return depthA == depthB && depthA >=0

where:

depthIfPerfect(node, parent):

    if degree(node) == 1:
        return 1;
    if degree(node) != 3:
        return -1; //not perfect

    let a and b be the neighbors that aren't parent

    let depthA = depthIfPerfect(a, node);
    let depthB = depthIfPerfect(b, node);
    
    if (depthA != depthB || depthA < 0):
        return -1: //not perfect
    return depthA+1;

You can mix the check for connectedness and acyclicity into this traversal if you like.

user_54835260
Related