Question

Please write a Java algorithm solving the following problem: Implement a Java method to check if a binary tree is balanced. For this assignment, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.

1. First, please create the following two classes supporting the Binary Tree Node and the Binary Tree:

public class BinTreeNode<T>

{

private T key;

private Object satelliteData;

private BinTreeNode<T> parent;

private BinTreeNode<T> leftChild;

private BinTreeNode<T> rightChild;

public BinTreeNode<T>(<T> key, Object satelliteData); // constructor

…

}

supporting the following public methods:

public void addLeftChild(BinTreeNode leftChildNode);

public void addRightChild(BinTreeNode rightChildNode);

public void setParent(BinTreeNode parentNode);

public BinTreeNode<T> getParent();

public BinTreeNode<T> getLeftChild();

public BinTreeNode<T> getRightChild();

and

public class BinTree<T> {

private BinTreeNode<T> root;

…

}

supporting the following methods

public BinTreeNode<T> getRoot();

public void setRoot(BinTreeNode<T>);

2. Add method public boolean isBalanced() 2 to the class BinTree, which returns true if the tree is balanced, and false otherwise.

Answer 1

public boolean isBalanced()
{
   return isBalanced(getRoot());
}
public boolean isBalanced(BinTreeNode<T> node)
{
int lh; /* for height of left subtree */
  
int rh; /* for height of right subtree */
  
/* If tree is empty then return true */
if (node == null)
return true;
  
/* Get the height of left and right sub trees */
lh = height(node.getLeftChild());
rh = height(node.getRightChild());
  
if (Math.abs(lh - rh) <= 1
&& isBalanced(node.getLeftChild())
&& isBalanced(node.getRightChild()))
return true;
  
/* If we reach here then tree is not height-balanced */
return false;
}
//helper method
int height(BinTreeNode<T> node)
{
/* base case tree is empty */
if (node == null)
return 0;
  
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + Math.max(height(node.getLeftChild()), height(node.getRightChild()));
}