Determine whether a given binary tree is fully populated, where "fully populated" means that every internal node has exactly two children, and all terminal nodes are at the same depth.

Question

Anonymous · Accepted Answer

When I started solving this one, I briefly considered (and verbalized) the idea of just counting the nodes in the tree, determining the height, and checking to see if node_count == 2^height - 1. In retrospect, that would have been a slick solution.

The actual solution I implemented was recursive; note that a fully populated binary tree has two fully populated subtrees as children. You also have to check whether the subtrees are the same height.

Solved · Answer

int getBalancedHeight(node * root){ if(root==NULL) return 0; if(root->left==NULL && root->right ==NULL) return 1; if(root->left==NULL || root->right==NULL) return -1; int lheight = getBalancedHeight(root->left); int rheight = getBalancedHeight(root->right); if(lheight<0 || rheight<0 || leheight!=lHeight) return -1; return leight+1; } The function returns -1, if not a full balanced tree. else return height of tree.

Microsoft

Microsoft Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches