LeetCode Medium: Count Complete Tree Nodes

Here is one LeetCode Medium level problem (Problem # 222: Count Complete Tree Nodes) which is an actual 2 liner to solve when solved recursively:

/**
 * 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 int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

This solution is O(n) in number of nodes in the binary tree and is a generic solution that can be used to solve any binary tree for that matter.

The fact that this is a complete binary tree, brings to my mind another solution approach with O((lg n)^2) solution which I'll share here very soon!

Until next time,

Stay Tuned and Happy Coding!

See ya later!!

LeetCode Problem #441. Arranging Coins

Here is my solution on LeetCode Problem #441. Arranging Coins 

Approach 1: Based on binary search and inequalities

class Solution {
    public int arrangeCoins(int N) {
        long minLevel = 0;
        long maxLevel = N;
        while (minLevel<maxLevel) {
            long midLevel = minLevel + (maxLevel-minLevel+1)/2;
            boolean predicate = ((midLevel*midLevel + midLevel) > (2*(long)N));
            
            if (predicate) {
                maxLevel = midLevel-1;
            }
            else {
                minLevel = midLevel;
            }
        }
        
        if ((minLevel*minLevel + minLevel) > (2*(long)N))
            return -1;
        return (int)minLevel;
    }
}

The time complexity is super-fast: O(lg n) where n is the the input N(the number of coins) and I don't think it can get any faster iteratively.

The only other faster solution I can think of is using SriDharacharya formula to find the roots to inequality:

l^2 + l <= 2*N

where l = last complete level

Do share your thoughts below!

<3
~Take Care

LeetCode Medium: Lowest Common Ancestor of a Binary Tree

My Solution for LeetCode medium problem #236: Lowest Common Ancestor of a Binary Tree, based on tree-recursion:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        boolean leftHasP = hasDescendant(root.left, p.val);
        boolean leftHasQ = hasDescendant(root.left, q.val);
        boolean rightHasP = hasDescendant(root.right, p.val);
        boolean rightHasQ = hasDescendant(root.right, q.val);
        
        if (root.val == p.val || root.val == q.val)
            return root;
        if ((leftHasP && rightHasQ) || (leftHasQ && rightHasP))
            return root;
        if (!leftHasP && !leftHasQ)
            return lowestCommonAncestor(root.right, p, q);
        else
            return lowestCommonAncestor(root.left, p, q);
        
    }
    
    private boolean hasDescendant(TreeNode root, int val) {
        if (root == null)
            return false;
        
        if (root.val == val) {
            return true;
        }
        if (hasDescendant(root.left, val) || hasDescendant(root.right, val)) {
            return true;
        }
        
        return false;
    }
}

Feel free to share your thoughts in comments, below!

LeetCode Medium: Construct Binary Tree from Inorder and Postorder Traversal

When we are given Inorder traversal of nodes in a tree, along with 1 other traversal, either preorder or postorder,  we can derive the original tree structure from the provided information.

I have solved the following LeetCode problem with the same idea in mind. Grab a look:

Problem #106: Construct Binary Tree from Inorder and Postorder Traversal 

/**
 * 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 buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length==0)
            return null;
        TreeNode root = treeFromInorderPostorder(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
        return root;
    }
    
    private TreeNode treeFromInorderPostorder(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        
        int inRootIdx = inStart;
        for (int i=inStart; i<=inEnd; i++) {
            if (inorder[i]==rootVal) {
                inRootIdx = i;
                break;
            }
        }
        // assert(inRootIdx != -1);
        int nodesInLeftSubtree = inRootIdx - inStart;
        if (nodesInLeftSubtree == 0) {
            root.left = null;
        } else {
        root.left = treeFromInorderPostorder(inorder, inStart, inRootIdx-1, postorder, postStart, postStart+nodesInLeftSubtree-1);
        }
        
        int nodesInRightSubtree = inEnd - inRootIdx;
        if (nodesInRightSubtree == 0) {
            root.right = null;
        } else {
        root.right = treeFromInorderPostorder(inorder, inRootIdx+1, inEnd, postorder, postStart+nodesInLeftSubtree, postEnd-1);
        }
        
        return root;
    }
}

In the similar vein, consider a previously solved problem:

Problem #105: Construct Binary Tree from Preorder and Inorder Traversal

The bounds for parameters with which to make recursive calls in these problems can be slightly tricky to understand so one needs to be careful with those.

Besides that, as always, let me know in comments if you find these solutions helpful or have ideas for improvement.

Toodles!

LeetCode medium: Construct Binary Tree from Preorder and Inorder Traversal

When we are given Inorder traversal of nodes in a tree, along with 1 other traversal, either preorder or postorder,  we can derive the original tree structure from the provided information.

I have solved the following LeetCode problem with the same idea in mind:

Problem #105: LeetCode medium: Construct Binary Tree from Preorder and Inorder Traversal

/**
 * 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 buildTree(int[] preorder, int[] inorder) {
        if (inorder.length == 0 || preorder.length==0)
            return null;
        TreeNode root = treeFromInorderPreorder(inorder, 0, inorder.length-1, preorder, 0, preorder.length-1);
        return root;
    }
    
    private TreeNode treeFromInorderPreorder(int[] inorder, int inStart, int inEnd, int[] preorder, int preStart, int preEnd) {
        
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        
        int inRootIdx = inStart;
        for (int i=inStart; i<=inEnd; i++) {
            if (inorder[i]==rootVal) {
                inRootIdx = i;
                break;
            }
        }
        // assert(inRootIdx != -1);
        int nodesInLeftSubtree = inRootIdx - inStart;
        if (nodesInLeftSubtree == 0) {
            root.left = null;
        } else {
        root.left = treeFromInorderPreorder(inorder, inStart, inRootIdx-1, preorder, preStart+1, preStart+1+nodesInLeftSubtree);
        }
        
        int nodesInRightSubtree = inEnd - inRootIdx;
        if (nodesInRightSubtree == 0) {
            root.right = null;
        } else {
        root.right = treeFromInorderPreorder(inorder, inRootIdx+1, inEnd, preorder, preStart+nodesInLeftSubtree+1, preEnd);
        }
        
        return root;
    }
}

In the similar vein, consider:

Problem #106: Construct Binary Tree from Inorder and Postorder Traversal

The bounds for parameters with which to make recursive calls can be slightly tricky to understand so one needs to be careful with those.

Besides that, as always, let me know in comments if you find these solutions helpful or have ideas for improvement.

Toodles!...

LeetCode Medium: Binary Tree Level Order Traversal

Here is my solution to LeetCode Problem #102: Binary Tree Level Order Traversal based on BFS traversal with modification -

/**
 * 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 List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
            int levelSize = q.size();
            List<Integer> level = new ArrayList<> ();
            for (int i=0; i<levelSize; i++) {
                TreeNode current = q.remove();
                level.add(current.val);
                if (current.left != null) q.add(current.left);
                if (current.right != null) q.add(current.right);
            }
            res.add(level);
        }
        
        return res;
    }
}

Try these related problems too:

https://chandniverma.blogspot.com/2020/06/leetcode-medium-binary-tree-right-side.html

LeetCode: More problems on Trees

Here are my Java solutions to more problems on trees. Following are 2 related ones:

Problem #104: Maximum Depth of Binary Tree

/**
 * 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 int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        
        int lDepth = maxDepth(root.left);
        int rDepth = maxDepth(root.right);
        
        return Math.max(lDepth, rDepth)+1;
    }
}

Problem #543: Diameter of a Binary Tree

/**
 * 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 {
    
    private int height(TreeNode root) {
        if (root == null)
            return -1;
        
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null)
            return 0;
        
        int lHeight = height(root.left);
        int rHeight = height(root.right);
        int lDiameter = diameterOfBinaryTree(root.left);
        int rDiameter = diameterOfBinaryTree(root.right);
        
        return Math.max(lHeight+rHeight+2 , Math.max(lDiameter, rDiameter));
    }
}

~~~

I plan to extend this category of posts with more related ones to come soon!

Until then,

Happy Problem Solving!!