Check if a tree is balanced

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one

My initial thoughts:
Do a DFS on the tree. Keep record of minimum level and maximum level. After DFS is done, check if max – min is less than or equal to one.

My initial codes:

	public static boolean isBalanced(TreeNode<Integer> root) {
		Pair<Integer> pair = DFSwithLevel(root, 0, Integer.MAX_VALUE,
				Integer.MIN_VALUE);
		return pair.getY() - pair.getX() <= 1;
	}

	private static Pair<Integer> DFSwithLevel(TreeNode<Integer> current,
			int level, int min, int max) {
		if (current.isLeaf()) {
			if (level < min)
				min = level;
			if (level > max)
				max = level;
			return new Pair<Integer>(min, max);
		} else {
			for (TreeNode<Integer> child : current.getChildren()) {
				Pair<Integer> pair = DFSwithLevel(child, level + 1, min, max);
				if (pair.getX() < min)
					min = pair.getX();
				if (pair.getY() > max)
					max = pair.getY();
			}
			return new Pair<Integer>(min, max);
		}
	}

Solution:

	private static int getMinLevel(TreeNode<Integer> root) {
		if (root.isLeaf())
			return 0;
		else {
			int min = Integer.MAX_VALUE;
			for (TreeNode<Integer> child : root.getChildren()) {
				min = Math.min(1 + getMinLevel(child), min);
			}
			return min;
		}
	}

	private static int getMaxLevel(TreeNode<Integer> root) {
		if (root.isLeaf())
			return 0;
		else {
			int max = Integer.MIN_VALUE;
			for (TreeNode<Integer> child : root.getChildren()) {
				max = Math.max(1 + getMaxLevel(child), max);
			}
			return max;
		}
	}

	public static boolean isBalanced2(TreeNode<Integer> root) {
		int maxLevel = getMaxLevel(root);
		int minLevel = getMinLevel(root);
		return maxLevel - minLevel <= 1;
	}

Comments: slightly more elegant than mine in that it utilizes the recursive structures of counting tree levels.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: