Practice-It

Write a method called stretch that stretches each node that has only one child in a binary tree of integers. More specifically, each node that has a single child should be replaced by a new node storing the data 1 and with the old node as a child in the same direction as the original node's child. For example, suppose a variable t stores a reference to the following tree:

                                 +----+
                                 | 13 |
                                 +----+
                              /          \
                      +----+                +----+
                      | 48 |                | 17 |
                      +----+                +----+
                     /                            \
                +----+                            +----+
                | 82 |                            | 23 |
                +----+                            +----+
               /      \
          +----+      +----+
          | 65 |      | 10 |
          +----+      +----+

There are two nodes in this tree that have a single child: the nodes storing 48 and 17. Each of those nodes is replaced in the tree with a new node storing the value 1 and with the original node as a child in the same direction as its only child. The node storing 48 has a left child, so it appears to the left of a new node storing 1. The node 17 has a right child, so it appears to the right of a new node storing 1. So after the call:

        t.stretch();

The tree should look like this:

                                       +----+
                                       | 13 |
                                       +----+
                                    /          \
                            +----+                +----+
                            |  1 |                |  1 |
                            +----+                +----+
                          /                              \
                    +----+                              +----+
                    | 48 |                              | 17 |
                    +----+                              +----+
                   /                                          \
              +----+                                          +----+
              | 82 |                                          | 23 |
              +----+                                          +----+
             /      \
        +----+      +----+
        | 65 |      | 10 |
        +----+      +----+

This stretching process should be performed on every node in the original tree that has a single child.

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

            // post: constructs an IntTreeNode with the given data and links
            public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
                this.data = data;
                this.left = left;
                this.right = right;
            }
        }

        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 to change the data field of the existing nodes in the tree. You will, however, construct new nodes containing the value 1 to be inserted into the tree and you will change the links of the tree to include these new nodes.