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 Trees and Graphs: Problem #101: Symmetric Tree

The next problem on hit list is Problem #101: Symmetric Tree

Again, this can be solved using many approaches both recursively or iteratively.

Approach 1: My recursive solution with complexity O(n) where n is the total number of TreeNodes in the tree is as follows:

/**
 * 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 boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        
        if (root.left == null && root.right == null)
            return true;
        
        return isMirror (root.left, root.right);
    }
    
    private boolean isMirror(TreeNode r1, TreeNode r2) {
        if (r1 == null && r2 == null)
            return true;
        if ((r1 == null && r2 != null) || (r1 != null && r2 == null))
            return false;
        if (r1.val != r2.val)
            return false;
        
        boolean mirror = isMirror(r1.left, r2.right);
        if (mirror)
            mirror = isMirror(r1.right, r2.left);
        
        return mirror;
    }
}

Approach 2: An iterative solution approach making use of a BFS like queue insertion of node-pairs to check for equality when popped (again O(n)):

/**
 * 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 boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        
        if (root.left == null && root.right == null)
            return true;
        
        //iterative solution
        
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root.left);
        q.add(root.right);
        while(!q.isEmpty()) {
            TreeNode n1 = q.remove();
            TreeNode n2 = q.remove();
            
            if (n1 == null && n2 == null)
                continue;
            if ((n1 == null && n2 != null) || (n1 != null && n2 == null))
                return false;
            if (n1.val != n2.val)
                return false;
            
            q.add(n1.left);
            q.add(n2.right);
            q.add(n1.right);
            q.add(n2.left);
        }
        
        return true;
    }
}

That's not all! There are definitely more approaches to it. One which I can think of is using stacks. Feel free to share your solutions for the same.

As always, you can checkout my latest accepted solutions on leetcode at https://leetcode.com/chandniverma/ . All the best!

LeetCode Trees and Graphs: Problem #100: Same Tree

Today I plan to do some problems on trees. With that, I started with Same Tree.

Here's my recursive solution of the same:

/**
 * 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 boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null) {
            if (q == null)
                return true;
            return false;
        } else {
            if (q == null)
                return false;
        }
        
        if (p.val != q.val)
            return false;
        
        boolean sameTree = true;
        sameTree = isSameTree(p.left, q.left);
        
        if (sameTree)
            sameTree = isSameTree(p.right, q.right);
        
        return sameTree;
    }
}

Sweet and Simple!

Happy Coding!!

LeetCode Medium: Binary Tree Right Side View

Today I solved the Leetcode medium problem #199 Binary Tree Right Side View. Here's the solution of the same using Level order Traversal while keeping a track of the last element on each level:

/**
 * 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<Integer> rightSideView(TreeNode root) {
        List<Integer> rightVisibleList = new ArrayList<> ();
        if (root == null)
            return rightVisibleList;
        
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i=0; i<size; i++) {
                TreeNode out = q.poll();
                if (i == size-1)
                    rightVisibleList.add(out.val);
                
                if (out.left != null)
                    q.add(out.left);
                
                if (out.right != null)
                    q.add(out.right);
            }
        }
        
        return rightVisibleList;
        
    }
}

In case we were to solve it for Left Side View we would have just kept a track of the first element at each level and that would have done the deal!

Happy Coding until next time!

Leetcode Medium: Letter Combinations of a Phone Number

A few days back I coded a Leetcode medium problem: Letter Combinations of a Phone Number (problem #17) as follows:

import java.util.Hashtable;

class Solution {
    public List<String> letterCombinations(String digits) {
        ArrayDeque<String> res = new ArrayDeque<>();
        res.add("");
        
        Hashtable<Integer, String> ht = new Hashtable<>();
        ht.put(2, "abc");
        ht.put(3, "def");
        ht.put(4, "ghi");
        ht.put(5, "jkl");
        ht.put(6, "mno");
        ht.put(7, "pqrs");
        ht.put(8, "tuv");
        ht.put(9, "wxyz");
        
        letterCombinationsRecur(digits, 0, ht, res);
        return new ArrayList<String>(res);
    }
    
    private void letterCombinationsRecur(final String digits, int digPtr, final Hashtable<Integer, String> ht, final ArrayDeque<String> res) {
        
        if (digPtr==digits.length()) {
            if (res.peekFirst().equals(""))
                res.removeFirst();
            return;
        }
        
        int inputResCnt = res.size();
        ArrayList<String> resAL = new ArrayList<>(res);
        
        
        String newLastChars = ht.get(digits.charAt(digPtr) - '0');
        int nlcLen = newLastChars.length();
        for (int nlcIdx=0; nlcIdx<nlcLen; nlcIdx++) {
            
            for (int i=0; i<inputResCnt; i++) {
                res.add(resAL.get(i) + newLastChars.charAt(nlcIdx));
            }
            
        }
        
        for (int i=0; i<inputResCnt; i++) {
            res.removeFirst();
        }
        letterCombinationsRecur(digits, ++digPtr, ht, res);
        
    }
}

Today, I revisited that problem and thought I could use a simplified technique to solve the problem by modifying the above solution to rely less of Level Order BFS-like dequeue population and rely more over recursion. Here's the result that resultantly significantly simpler:

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0)
            return result;
        
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        letterCombinationsRecur (digits, 0, "", mapping, result);
        return result;
    }
    
    void letterCombinationsRecur (String digits, int digitPtr, String currentLetterCombination, String[] mapping, List<String> result) {
        if (digitPtr == digits.length()) {
            result.add(currentLetterCombination);
            return;
        }
        
        String currDigLetters = mapping[digits.charAt(digitPtr)-'0'];
        for (int i=0; i<currDigLetters.length(); i++) {
            letterCombinationsRecur(digits, digitPtr+1, currentLetterCombination+currDigLetters.charAt(i), mapping, result);
        }
    }
    
}

Let me know your thoughts in the comment section below! Meanwhile, happy coding!!

[Problem3 SPOJ:ROBOTGRI] A problem for lovers of mazes!

PROBLEM: http://www.spoj.com/problems/ROBOTGRI/

This was a tough nut!

Its a graph problem. Its actually a combination of 2 problems in one! I have voted it as hard and given it my recommendation.

I went through the following resources (none has the actual solution but all serve as hints) to finally come up with a solution for it:

https://www.cs.bu.edu/teaching/alg/maze/
https://www.hackerearth.com/practice/notes/dynamic-programming-problems-involving-grids/
http://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/
http://www.geeksforgeeks.org/count-number-ways-reach-destination-maze/
https://www.youtube.com/watch?v=PwxGTHraMNg&feature=youtu.be
http://www.geeksforgeeks.org/applications-of-breadth-first-traversal/



SOLUTION: https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-ROBOTGRI.cpp
Tested and Accepted: http://www.spoj.com/status/ROBOTGRI,chandniverma/

Time complexity in the worst case: O(n^2 + E)
where n = number of rows (or columns) in the grid
and E = number of edges in the connected graph containing the starting cell 'S'.

Space complexity: O(n^2)