Check if a binary tree is AVL tree

isavl.cpp

#include <iostream>
#include <stack>
#include <stdlib.h>

struct BTree {
  int value;
  int depth;
  BTree *left;
  BTree *right;
};

void fillDepth(BTree *mytree) {
  if (mytree == NULL) return;
  int ld = 0, rd = 0;
  if (mytree->left == NULL && mytree->right == NULL) {
    mytree->depth = 1;
  } else {
    if (mytree->left != NULL) {
      fillDepth(mytree->left);
      ld = mytree->left->depth;
    }
    if (mytree->right != NULL) {
      fillDepth(mytree->right);
      rd = mytree->right->depth;
    }
    if (ld > rd) {
      mytree->depth = ld + 1;
    } else {
      mytree->depth = rd + 1;
    }
  }
}

bool isAVLTree(BTree *mytree) {
  fillDepth(mytree);
  std::cout<<"depth: "<<mytree->depth<<std::endl;
  bool isSorted = true;
  bool isBalanced = true;
  int lTempDepth, rTempDepth;
  if (mytree == NULL) return true;
  std::stack<BTree*> s;
  BTree *t = mytree;
  s.push(t);
  while (!s.empty()) {
    std::cout<<"loop..."<<std::endl;
    t = s.top();
    s.pop();
    if (t->left != NULL) {
      s.push(t->left);
      if (t->left->value >= t->value) {
        isSorted = false;
      }
      lTempDepth = t->left->depth;
    } else {
      lTempDepth = 0;
    }
    if (t->right != NULL) {
      s.push(t->right);
      if (t->right->value <= t->value) {
        isSorted = false;
      }
      rTempDepth = t->right->depth;
    } else {
      rTempDepth = 0;
    }
    std::cout<<"left: "<<lTempDepth<<" right: "<<rTempDepth<<std::endl;
    if (abs(rTempDepth-lTempDepth) > 1) {
      isBalanced = false;
    }
  } // while

  if (isSorted && isBalanced) {
    return true;
  } else {
    return false;
  }
}

int main() {
  BTree *tree = new BTree;
  tree->value = 5;
  tree->left = new BTree;
  tree->left->value = 4;
  tree->left->right = NULL;
  tree->left->left = new BTree;
  tree->left->left->value = 3;
  tree->left->left->left = new BTree;
  tree->left->left->left->value = 2;
  tree->left->left->left->left = NULL;
  tree->left->left->left->right = NULL;
  tree->left->left->right = NULL;

  tree->right = new BTree;
  tree->right->value = 8;
  tree->right->left = new BTree;
  tree->right->left->value = 6;
  tree->right->left->left = NULL;
  tree->right->left->right = NULL;
  tree->right->right = new BTree;
  tree->right->right->value = 9;
  tree->right->right->left = NULL;
  tree->right->right->right = NULL;

  bool ok = isAVLTree(tree);
  std::cout<<"is AVL: "<<ok<<std::endl;
  return 0;
}

TODO: make fillDepth a non-recursive function