For valid AVL tree we just need to identify the difference of Max depth and Min depth should not grater than 1.
Example of valid AVL Tree is
A B C D E
Here root node is A and from A max depth is 3 and min depth is 2 so difference is 3-2 = 1 valid.
Example of invalid AVL Tree is
A B C D E F G H
Here in above tree max depth is 5 and min depth is 2 so diff is 5-2 = 3 its invalid AVL tree.
Algorithm
public static boolean isAVLTree(TreeNode root) { return (findMaxDepth(root) - findMinDepth(root)) <= 1; } public static int findMaxDepth(TreeNode root) { if (root == null) { return 0; } return 1 + Math.max(findMaxDepth(root.leftNode), findMaxDepth(root.rightNode)); } public static int findMinDepth(TreeNode root) { if (root == null) { return 0; } return 1 + Math.min(findMinDepth(root.leftNode), findMinDepth(root.rightNode)); }
Full Example
TreeNode.java
public class TreeNode { public String nodeName = ""; public boolean isVisited = false; public int value = 0; public TreeNode leftNode = null; public TreeNode rightNode = null; public TreeNode() { // TODO Auto-generated constructor stub } public TreeNode(String name) { nodeName = name; } public TreeNode(TreeNode left, TreeNode right, String name) { leftNode = left; rightNode = right; nodeName = name; } }
IsAVLTree.java
package com.omt.learn.algo; import com.omt.learn.algo.util.TreeNode; public class IsAVLTree { public static void main(String[] args) { TreeNode root = generateTree(); printTree(root); System.out.println("--------------\n\n"); System.out.println("Max Depth :" + findMaxDepth(root)); System.out.println("Min Depth :" + findMinDepth(root) + " \n\n"); System.out.println("--------------"); System.out.println("Is AVL Tree :" + isAVLTree(root)); } public static boolean isAVLTree(TreeNode root) { return (findMaxDepth(root) - findMinDepth(root)) <= 1; } public static int findMaxDepth(TreeNode root) { if (root == null) { return 0; } return 1 + Math.max(findMaxDepth(root.leftNode), findMaxDepth(root.rightNode)); } public static int findMinDepth(TreeNode root) { if (root == null) { return 0; } return 1 + Math.min(findMinDepth(root.leftNode), findMinDepth(root.rightNode)); } public static TreeNode generateTree() { // TreeNode AVL = new TreeNode(new TreeNode(new TreeNode("D"), new // TreeNode("E"), "B"), new TreeNode("C"), "A"); TreeNode notAVL = new TreeNode(new TreeNode(new TreeNode("D"), new TreeNode("E"), "B"), new TreeNode(null, new TreeNode(null, new TreeNode(null, new TreeNode("H"), "G"), "F"), "C"), "A"); return notAVL; } public static void printTree(TreeNode root) { int rootPosition = findMaxDepth(root) * 3; printTree(root, rootPosition); } public static void printTree(TreeNode root, int rootPosition) { if (root != null) { String s = getSpace(rootPosition) + root.nodeName; System.out.println(s); printTree(root.rightNode, rootPosition + 3); printTree(root.leftNode, rootPosition - 3); } } public static String getSpace(int n) { String s = ""; for (int i = 0; i < n; i++) { s += " "; } return s; } }