Categories
Algorithms Computer Science

Determine if tree is AVL in O(n)

The following java method will determine if a binary tree is AVL (and, obviously BST)

/**
 * This recursive method will calculate if a tree is AVL by returning
 * its max depth.
 *
 * @param t  
 * @param p 
 * @return Max depth of the binary tree if it's avl else -1
 **/
static int isAVL(Node t, int p){
  int fl = 0; // This is the left factor
  int fr = 0; // This is the right factor
  if(t.hasLeft()){
    if(key(t.leftChild() > key(t))) return -1;
    fl = isAVL(t.leftChild(), p + 1);
  }
  if(t.hasRight()){
    if(key(t.rightChild()) < key(t)) return -1;
    fr = isAVL(t.rightChild(), p + 1);
  }
  if(fr == -1 || fl == -1) return -1;
  if(abs(fr - fl) == 0 || abs(fr - fl) == 1) return max(fl, fr, p);
  else return -1;
}