My question is regarding Problem 4.33 (page 164) of the textbook Data Structures

Question

My question is regarding Problem 4.33 (page 164) of the textbook Data Structures and Algorithm Analysis in Java (3rd Edition).

"Write a recursive method which takes the reference to the root node of a tree T and returns a reference to the root node of the tree that results from removing all leaves from T."

How Node is being constructed

class Node {

      int data;

      Node left, right;

   /*

      * Constructs a leaf

      */

      Node(int key) {

      this(key, null, null);

      }

      /*

          * Constructs a Node

          */

      Node(int data, Node left, Node right) {

      this.data = data;

      this.left = left;

      this.right = right;

      }

      /*

          * Checks to see if node is a Leaf

*/

      boolean isLeaf() {

      return left == null && right == null;

      }

      }

//pre-defined

Node root;

int n;

Explanation / Answer

Here is the code for you:

Node removeLeaves(Node root)
{
if(root == null)   //If there are no nodes in the tree.
return null;
if(root.left == null && root.right == null)   //If there is only one node.
{
root = null;
return root;
}
removeLeaves(root.left);       //Call recursively for left subtree.
removeLeaves(root.right);   //Call recursively for right subtree.
return root;                //Finally, return the root.
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.