My solution to a “Daily Coding Problem” that I received in my mail today.

Given a binary tree where all nodes are either 0 or 1, prune the tree so that subtrees containing all 0s are removed.

For example, given the following tree:

   0
  / \
 1   0
    / \
   1   0
  / \
 0   0

should be pruned to:

   0
  / \
 1   0
    /
   1

We do not remove the tree at the root or its left child because it still has a 1 as a descendant.

Here’s my solution in Typescript, (fyi, I have solved this but I cannot fully visualise the solution in my head)

class BTNode<T> {
    val: T;
    left: BTNode<T> | null  = null;
    right: BTNode<T> | null = null;
    constructor(val: T){
        this.val = val;
    }
}   
oneFortySix() {
    //populate the tree
    let head = new BTNode<number>(3);
    head.left = new BTNode<number>(1);
    head.right = new BTNode<number> (4);
    head.right.right = new BTNode<number>(0);
    head.right.left = new BTNode<number>(0);
    console.log("Binary Tree head....");
    console.log(head);
    let prunedTree = this.removeLessThan1(head)? head : null;
    console.log("Binary Tree head (post prune) ....");
    console.log(prunedTree);
}
private removeLessThan1(root: any): boolean {
    if(root == null) {
        return false;
    }
    root = root as BTNode<number>;
    let a1: boolean = this.removeLessThan1(root.left);
    let a2: boolean = this.removeLessThan1(root.right);
    if(!a1) root.left = null;
    if(!a2) root.right = null;
    return root.val > 0 || a1 || a2;
}

Like the blog? Subscribe for updates

As usual, if you find any of my posts useful support me by  buying or even trying one of my apps on the App Store. 

https://mydaytodo.com/apps/

Also, if you can leave a review on the App Store or Google Play Store, that would help too.


0 Comments

Leave a Reply

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