Balanced Tree Problem

How would you check if a binary tree is balanced?

 

Solution:

A tree is considered balanced when the difference between the min depth and max depth does not exceed 1.

Recursive algorithms always work well on trees, so here’s some code.

int min_depth( Node * root ) {
    if( !root ) {
        return 0;
    }
    return 1 + min( min_depth( root->left ),
                    min_depth( root->right ));
}

int max_depth( Node * root ) {
    if( !root ) {
        return 0;
    }
    return 1 + max( max_depth( root->left ),
                            max_depth( root->right ));
} 

bool is_balanced( Node * root ) {
    return ( max_depth( root ) - min_depth( root ) ) <= 1
}

---

More Questions and Answers @ Cracking the Coding Interview: Fourth Edition (308 page e-book / PDF)

Delivered instantly as a PDF via email. For Software Engineers & SDETs      

·         150 programming interview questions and answers

·         5 proven approaches to crack algorithm questions

·         10 mistakes candidates make, and how to avoid them.

·         How to prepare for technical and behavioral questions without wasting your time!

30 Day Money Back Guarantee: Don't love the book? We'll give you your money back!
 

More Info