• Determine if BinaryTree is Balanced

This post will explore the problem of checking whether a binary tree is balanced or not. A binary tree is considered to be balanced if the height difference between two subtrees is no more than 1. This definition could be different depending on use cases. We will explore two approaches to this problem. One where all nodes are visited whereas the second approach takes advantage of early termination if one subtree is unbalanced.

Brute Force

The brute force approach will recursively visit every node using in-order traversal. For each node, the algorithm will get the height of its left subtree and right subtree. The greater height of the two is incremented by one, and is returned to the parent of the current node where the process repeats. The difference is computed one last time at the root and returns false if it is larger than one.

Implementation

public static boolean isBalanced(TreeNode root) {
if (root == null)
return true;

int leftHeight = treeHeight(root.left);
int rightHeight = treeHeight(root.right);
return Math.abs(leftHeight - rightHeight) <= 1;
}

Helper Method

private static int treeHeight(TreeNode root) {
if (root == null)
return 0;

int leftHeight = treeHeight(root.left);
int rightHeight = treeHeight(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}

Optimized

The optimized solution takes advantage of early termination in the event where one of the subtrees is detected to be unbalanced. When this occurs, the unbalanced status is passed to the parent and eventually the root. At the point where the unbalanced status is detected, there is no need to check for any other subtree.

TreeNodeAttributes Definition

public static class TreeNodeAttributes {
boolean isBalanced;
int height;

public TreeNodeAttributes(isBalanced, height) {
isBalanced = isBalanced;
height = height;
}
}

Implementation

public static boolean isBalanced(TreeNode root) {
return getAttributes(root).isBalanced;
}

Helper Method

public static TreeNodeAttributes getAttributes(TreeNode root) {
if (root == null)
return new TreeNodeAttributes(true, 0);

TreeNodeAttributes leftAttr = getAttributes(root.left);
if (!leftAttr.isBalanced)
return leftAttr;

TreeNodeAttributes rightAttr = getAttributes(root.right);
if (!rightAttr.isBalanced)
return rightAttr;

TreeNodeAttributes curAttributes = new TreeNodeAttributes();
curAttributes.height = Math.max(leftAttr.height, rightAttr.height) + 1;
curAttributes.isBalanced = Math.abs(leftAttr.height - rightAttr.height) <= 1;

return curAttributes;
}
• Letter is Constructible from Magazine

The problem in this post is concerned with answering the question of whether a given letter can be reconstructed with a given magazine. The letter is reconstructible when a...

• Palindromic Permutation

This post explores the question of if the characters of a given word can rearranged such that the final word is a palindrome. For example, the word "edified" coul...

• Convert Roman Numeral to Integer and Vice Versa

This post will explore the situations where there is a need to convert a roman numeral to integer and vice versa. The common basic symbols in the roman numeral system are I...

• Palindrome Integer

Given an integer, determine if it is a palindrome number.

Approaches

There are a couple of methods in approaching this problem. The first thing that comes ...

• Lowest Common Ancestor of Two Nodes in a Binary Tree

Any two nodes in a binary tree has the root node as a common ancestor, assuming both nodes are in the same tree. The lower common ancestor node is the furthest node from th...

• Singleton Design Pattern

The singleton design pattern is classified as a creational pattern. It is appropriate for scenario where only one copy of the class is needed because singleton enforces tha...

• Reverse an Integer

Given an integer, compute and return its reverse form. This problem becomes a regular reversal problem if the integer is converted into a string to get its character array....

• Abstract Factory Design Pattern

The Abstract Factory Design Pattern is classified as a creational pattern and is similar to the Factory Design Pattern in a sense that Abstract Factory creates other factor...

• Factory Design Pattern

The Factory Design Pattern is one of the most used design patterns. It is classified as a creational pattern under the Gang of Four (GoF). The intention behind the Factory ...

• Perfect Squares and ℤ/ℝ Square Roots

This post will explore how the binary search algorithm can help us check if a given number is a perfect square, find the integer square root of a given number, and find the...

• BinarySearch in JAVA

When given a sorted list of numbers, binary search is the best algorithm to have in your arsenal. The binary search finds the target element in O(log(n)) time by taking adv...

• SelectionSort in JAVA

Today, I will be show another comparative sorting algorithm known as Selection Sort. Selection sort works by finding a smaller element downstream from the current element a...

• BinaryTree PreOrder Traversal in JAVA

PreOrder traversal is very similar to in-order traversal in terms of code. The idea behind pre-order traversal is to do all the processing before visiting the left subtree ...

• Next Greater Element in Linear Time in JAVA

This is my implementation of the algorithm for that gets the next greater element than the current element in linear time. For elements with no next greater element, match ...