aboutsummaryrefslogtreecommitdiff
path: root/balanced_binary_tree.c
blob: c42ec006dcc87fbdb9c2756ac789faea182eda2e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 110. Balanced Binary Tree
#include "leetcode.h"

// given a binary tree, determine if it is height balanced

int depth(struct TreeNode *root) {
  if (!root)
    return 0;
  return fmax(depth(root->left), depth(root->right)) + 1;
}

bool isBalanced(struct TreeNode *root) {
  if (!root)
    return true;
  return isBalanced(root->left) && isBalanced(root->right) &&
         !(abs(depth(root->left) - depth(root->right)) > 1);
}

int main() {
  int r1i[] = {3, 9, 20, -1, -1, 15, 7}, r2i[] = {1, 2, 2, 3, 3, -1, -1, 4, 4};
  struct TreeNode *r1 = treenode_build(r1i, ARRAY_SIZE(r1i));
  struct TreeNode *r2 = treenode_build(r2i, ARRAY_SIZE(r2i));
  printf("%d\n", isBalanced(r1)); // expect: 1
  printf("%d\n", isBalanced(r2)); // expect: 0
  treenode_free(r1);
  treenode_free(r2);
}