Practice-It

Write a method called limitLeaves that takes an integer n as a parameter and that removes nodes from a tree to guarantee that all leaf nodes store values that are greater than n. For example, suppose a variable t stores a reference to the following tree:

                                 +----+
                                 | 13 |
                                 +----+
                               /        \
                        +----+            +----+
                        | 18 |            | 10 |
                        +----+            +----+
                       /                 /      \
                  +----+           +----+        +----+
                  | 82 |           | 17 |        | 23 |
                  +----+           +----+        +----+
                 /      \                \             \
             +----+    +----+           +----+        +----+
             | 92 |    |  8 |           | 12 |        | 20 |
             +----+    +----+           +----+        +----+
        

And we make the following call:

            t.limitLeaves(20);
        

Then your method must guarantee that all leaf node values are greater than 20. So it must remove the leaves that store 8, 12, and 20. But notice that this creates a new leaf that stores 17 when its child is removed. This new leaf must also be removed. Thus, we end up with this tree:

                                 +----+
                                 | 13 |
                                 +----+
                               /        \
                        +----+            +----+
                        | 18 |            | 10 |
                        +----+            +----+
                       /                        \
                  +----+                         +----+
                  | 82 |                         | 23 |
                  +----+                         +----+
                 /
             +----+
             | 92 |
             +----+
        

Notice that the nodes storing 13, 18, and 10 remain even though those values are not greater than 20 because they are branch nodes. Also notice that you might be required to remove nodes at many levels. For example, if the node storing 23 instead had stored the value 14, then we would have removed it as well, which would have led us to remove the node storing 10.

Your method should remove the minimum number of nodes that satisfies the constraint that all leaf nodes store values greater than the given n.

You are writing a public method for a binary tree class defined as follows:

            public class IntTreeNode {
                public int data;          // data stored in this node
                public IntTreeNode left;  // reference to left subtree
                public IntTreeNode right; // reference to right subtree

                
            }

            public class IntTree {
                private IntTreeNode overallRoot;

                
            }
        

You are writing a method that will become part of the IntTree class. You may define private helper methods to solve this problem, but otherwise you may not assume that any particular methods are available. You are not allowed to change the data fields of the existing nodes in the tree (what we called "morphing" in assignments 7 and 8), you are not allowed to construct new nodes or additional data structures, and your solution must run in O(n) time where n is the number of nodes in the tree.