Trouble understanding recursion in finding if a binary tree is balanced
int cntHeight(TreeNode *root) {
if(root == NULL) return 0;
int l = cntHeight(root->left);
int r = cntHeight(root->right);
if(l < 0 || r < 0 || abs(l-r) > 1) return -1;
else return max(l, r) + 1;
}
bool isBalanced(TreeNode *root) {
return cntHeight(root) >= 0;
}
I have found this solution in C to check if a binary tree is balanced.
However, I am having a very hard time visualizing how this algorithm works
entirely. For that reason, there are two things I am uncertain about.
Does the algorithm recurse in the middle of the tree and not just the sides?
I noticed that only max(1, r) is called, don't we need to find the min as
well?
Furthermore, how would you even go about developing an algorithm like
this? I wouldn't know how to come up with a solution like this..
No comments:
Post a Comment