Authors:
Stuart Reges, Marty Stepp
Chapter:
Binary Trees
Exercise:
Exercises
Question:17 | ISBN:9780136091813 | Edition: 2
Question
Write a method called tighten that eliminates branch nodes that have only one child. Each such node should be replaced by its only child. (This can lead to multiple replacements because the child might itself be replaced.) For example, if a variable called t refers to reference tree #2, the call of t.tighten(); should leave t storing the following tree.
Add the above method to the IntTree class from this chapter. You may define additional private methods to implement your public method if necessary. Several problem descriptions refer to the following reference binary trees:
Answer
Implementation of tighten method:
public void tighten()
{
overallRoot = tighten(overallRoot);
}
private IntTreeNode tighten(IntTreeNode root)
{
if(root == null)
return root;
root.left = tighten(root.left);
root.right = tighten(root.right);
if(root.left == null && root.right != null)
{
root = root.right;
}
else if(root.left != null && root.right == null)
{
root = root.left;
}
return root;
}