Binary Tree Pruning

Have an on-line call at 02:30 PM. I believe I am well prepared. Will see how it goes.

Earlier today I selected LeetCode 814 Binary Tree Pruning problem.

We are given the head node root of a binary tree, 
where additionally every node's value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) 
not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Note:

o The binary tree will have at most 200 nodes.
o The value of each node will only be 0 or 1.

We are given a binary tree whose nodes are holding 0 or 1 as value. We need to prune the BT as described in the requirements. If you are interested in this problem please navigate to the LeetCode web site and read the actual requirements. In addition LeetCode has a set of test cases.

In this post we will solve the problem using the Java programming language on a Windows 10 computer using the VSCode IDE. You can use any of the languages supported by LeetCode and solve the problem on the LeetCode side with the IDE provided.

Since I am going to solve the problem on my computer I will need to generate test scaffolding. Note that such code IS NOT PART OF THE SOLUTON.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        
    }
}

The signature for the method in question is as expected. In addition we will be using the TreeNode class to represent and manipulate the binary tree.

1,null,0,0,1
main <<< strArr: [1, null, 0, 0, 1]
main <<<    arr: [1, null, 0, 0, 1]
main <<< bt levelOrder:
1
0
0,1
main <<< pruned levelOrder:
1
0
1


1,0,1,0,0,0,1
main <<< strArr: [1, 0, 1, 0, 0, 0, 1]
main <<<    arr: [1, 0, 1, 0, 0, 0, 1]
main <<< bt levelOrder:
1
0,1
0,0,0,1
main <<< pruned levelOrder:
1
1
1


1,1,0,1,1,0,1,0
main <<< strArr: [1, 1, 0, 1, 1, 0, 1, 0]
main <<<    arr: [1, 1, 0, 1, 1, 0, 1, 0]
main <<< bt levelOrder:
1
1,0
1,1,0,1
0
main <<< pruned levelOrder:
1
1,0
1,1,1


0,null,0,0,0
main <<< strArr: [0, null, 0, 0, 0]
main <<<    arr: [0, null, 0, 0, 0]
main <<< bt levelOrder:
0
0
0,0
main <<< pruned levelOrder:

The input line per test contains a single line with the depth first traversal of the nodes in the binary tree. This technique is typically used by LeetCode to define binary trees.

Our test scaffold seems to read and parse the input line. The values are placed in a String[] array. Using the String[] array we appear to create a Integer[] and populate it with the same values. The two arrays are displayed.

We then appear to generate and populate a binary tree with the values from the Integer[] array. The binary tree is displayed in level order. The display seems to match the specified values.

We then seem to make a call to the method in question to prune the binary tree. The resulting binary tree is then displayed.

While looking at the test cases and associated diagrams I noticed the end case in which all the nodes in the binary tree may need to be pruned. I forgot the condition before I submitted the code. After addressing the issue the code was accepted by LeetCode.

    /**
     * Test scaffolding
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read String[] with node values for binary tree ****
        String[] strArr = br.readLine().trim().split(",");

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< strArr: " + Arrays.toString(strArr));

        // **** create and populate Integer[] ****
        Integer[] arr = new Integer[strArr.length];
        for (int i = 0; i < strArr.length; i++) {
            if (strArr[i].equals("null"))
                arr[i] = null;
            else
                arr[i] = Integer.parseInt(strArr[i]);
        }

        // ???? ????
        System.out.println("main <<<    arr: " + Arrays.toString(arr));

        // **** create and populate a original binary tree ****
        BST bt = new BST();
        bt.root = bt.populate(arr);
    
        // ???? ????
        System.out.println("main <<< bt levelOrder:");
        System.out.println(bt.levelOrder());

        // **** prune the BT ****
        bt.root = pruneTree(bt.root);

        // ???? ????
        System.out.println("main <<< pruned levelOrder:");
        System.out.println(bt.levelOrder());
    }

The test scaffold seems to follow (what a surprise) our description while looking at the test cases. Note that we create the binary tree using the BST class. Such code is only used in the test scaffold. As usual all the code can be found in the associated GitHub repository (https://github.com/JohnCanessa/BinaryTreePrunning) for this post.

    /**
     * Return the same tree where every subtree (of the given tree) 
     * not containing a 1 has been removed.
     * 
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 36.5 MB, less than 77.69% of Java online submissions.
     */
    static TreeNode pruneTree(TreeNode root) {
      
        // **** sanity check ****
        if (root == null)
            return null;

        // **** recursive call ****
        prune(root);

        // **** delete root node (if needed) ****
        if (leafNode(root))
            root = null;

        // **** returned pruned BT ****
        return root;
    }

The idea is to perform a depth first search traversal on the binary tree. We will be checking and pruning nodes.

After the sanity check we prune the binary tree. If we end with a root node with value 0 (end conditioned that I initially forgot to code) we set the root of the binary tree to null (pruned). The binary tree is then returned.

    /**
     * DFS traversal deleting nodes.
     * Recursive call.
     */
    static void prune(TreeNode root) {
        if (root != null) {

            // **** visit left sub tree ****
            prune(root.left);

            // **** delete left node (if needed) ****
             if (root.left != null && leafNode(root.left))
                root.left = null;

            // **** visit right sub tree ****
            prune(root.right);

            // **** delete right node (if needed) ****
            if (root.right != null && leafNode(root.right))
                root.right = null;
        } 
    }

The prune() method implements DFS in a recursive fashion. We traverse the left and then the right subtrees. After each traversal we prune the left or the right node as needed.

    /**
     * Auxiliary method.
     */
    static boolean leafNode(TreeNode root) {

        // **** sanity check ****
        if (root.val == 1)
            return false;

        // **** check if end node ****
        if (root.left == null && root.right == null)
            return true;
  
        // **** not a leaf node ****
        return false;
    }

This is an auxiliary method. We only prune a node with value 0 if it is a leaf node. That implies it has no children that meets the requirements.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 6,488 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.

Regards;

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.