Implement a function to check if a tree is balanced, valid AVL Tree.

May 1, 2016 by omt

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;
	}

}