Leetcode: Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Understand the problem:
The naive solution is to maintain a sliding window with size k, when we add an element nums[i], compare the nums[i] with each element in the window. If it is less or equal to t, return true. We return true because the distance between i and each element in the window must be less or equal to k. The complexity of this solution would be O(nk). 

We could use a treeSet to improve the complexity. The treeSet is essentially a balanced binary search tree. We put k elements in the treeSet, which is a sliding window. So when we insert an element to the treeSet, we need to remove one from the end. 

So the basic idea is for each element nums[i], we check if there is any element between [nums[i] - t, nums[i] + t]. If yes, return true.

Code (Java):

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length <= 1 || k <= 0 || t < 0) {
            return false;
        }
        
        TreeSet<Integer> treeSet = new TreeSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            Integer floor = treeSet.floor(nums[i] + t);
            Integer ceil = treeSet.ceiling(nums[i] - t);
            
            if ((floor != null && floor >= nums[i]) 
                || (ceil != null && ceil <= nums[i])) {
                return true;
            }
            
            treeSet.add(nums[i]);
            
            if (i >= k) {
                treeSet.remove(nums[i - k]);
            }
        }
        
        return false;
    }
}

Leetcode: Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Idea:
Obviously, the question asks for a BFS. The major difference from the traditional BFS is it only prints the right-most nodes for each level. Consequently, the basic idea is to add right child before adding the left child. For each level, only print out the first node, which must be the right-most node. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if (i == 0) {
                    result.add(curr.val);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
                
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
            }
        }
        
        return result;
    }
}

A DFS solution: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        
        if (root == null) {
            return result;
        }
        
        rightSideViewHelper(root, 0, result);
        
        return result;
    }
    
    private void rightSideViewHelper(TreeNode root, int level, List<Integer> result) {
        if (root == null) {
            return;
        }
        
        if (level == result.size()) {
            result.add(root.val);
        }
        
        rightSideViewHelper(root.right, level + 1, result);
        rightSideViewHelper(root.left, level + 1, result);
    }
}

Leetcode: Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Understand the problem:
The problem asks for the sum of all root-to-leaf numbers. The problem itself is not hard to understand. Use DFS is the natural way. The only thing to note is the overflow problem, so we may use a long long to store the intermediate results.

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    long pathSum = 0;
    public int sumNumbers(TreeNode root) {

        sumNumbersHelper(root, 0);
        
        return (int)pathSum;
    }
    
    private void sumNumbersHelper(TreeNode root, long curSum) {
        if (root == null) {
            return;
        }
        
        curSum = curSum * 10 + root.val;
        
        if (root.left == null && root.right == null) {
            pathSum += curSum;
        }

        sumNumbersHelper(root.left, curSum);
        sumNumbersHelper(root.right, curSum);
    }
}

Update on 10/8/14:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumNumbers(TreeNode root) {

        return sumNumbersHelper(root, 0);
    }
    
    private int sumNumbersHelper(TreeNode root, int preSum) {
        if (root == null) {
            return 0;
        }
        
        int curSum = root.val + preSum * 10;
        
        if (root.left == null && root.right == null) {
            return curSum;
        }
        
        return sumNumbersHelper(root.left, curSum) + sumNumbersHelper(root.right, curSum);
    }
}

Leetcode: Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Understand the problem:
This is a follow-up problem of the problem 1. The mainly difference is now the tree is not perfect binary tree any more. Note that you are still required to use constant extra space. 
So if space is not a problem, we may still use a queue to do a BFS. 

Solution:
Since now each node may not have its left or right child, the previous approach may not work. The key of the solution is to find a valid next node. 

Code (Java):

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
        }
        
        TreeLinkNode p = root;
        
        while (p.next != null && p.next.left == null && p.next.right == null) {
            p = p.next;
        }
        
        
        if (root.right != null && p.next != null) {
            if (p.next.left != null) {
                root.right.next = p.next.left;
            } else if (p.next.right != null){
                root.right.next = p.next.right;
            }
        } else if (root.left != null && p.next != null) {
            if (p.next.left != null) {
                root.left.next = p.next.left;
            } else if (p.next.right != null) {
                root.left.next = p.next.right;
            }
        }
        
        connect(root.right);
        connect(root.left);
    }
}

Discussion:
The only tricks here is to go to its right child first then its left right, i.e, connect right pointers at each level backward. That is because we wanna find the first valid node. We can use an example to illustrate this. If we go to the left child before right one, 

Input:	{2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}
Output:	{2,#,1,3,#,0,7,9,1,#,2,1,0,#,7,#}
Expected:	{2,#,1,3,#,0,7,9,1,#,2,1,0,8,8,#,7,#}

Why? That is because when we are at Node 7, we figure out the p pointer points to node 9. However, since now 9 is not connected to 1 yet, so node 7's right child, 0 cannot point to node 1's left child, which is 8. That is why we must traverse the right node first to make 9 connects to 1 before we check the node 7.


Update on 9/18/15:

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
        }
        
        if (root.next != null) {
            TreeLinkNode p = root;
            while (p.next != null && p.next.left == null && p.next.right == null) {
                p = p.next;
            }
            
            if (p.next != null) {
                p = p.next;
            }
            
            if (root.right != null) {
                if (p.left != null) {
                    root.right.next = p.left;
                } else if (p.right != null) {
                    root.right.next = p.right;
                }
            } else if (root.left != null) {
                if (p.left != null) {
                    root.left.next = p.left;
                } else if (p.right != null) {
                    root.left.next = p.right;
                }
            }
        }
        
        connect(root.right);
        connect(root.left);
    }
}

Update on 2/8/16:
Constant space solution:

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        TreeLinkNode curr = root;
        TreeLinkNode dummyNode = new TreeLinkNode(0);
        TreeLinkNode pre = dummyNode;
        
        while (curr != null) {
            TreeLinkNode p = curr;
            while (p != null) {
                if (p.left != null) {
                    pre.next = p.left;
                    pre = pre.next;
                }
                
                if (p.right != null) {
                    pre.next = p.right;
                    pre = pre.next;
                }
                
                p = p.next;
                
                if (p == null) {
                    curr = dummyNode.next;
                    pre = dummyNode;
                    dummyNode.next = null;
                }
            }
        }
        
    }
}

Leetcode: Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Understand the problem:
The problem asks for populating each of node's next pointer to its next right node. If there is no next node, its next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note that you are required to only use constant extra space. 

A native approach:
A very straight-forward solution is to use BFS, where we traverse the tree in level-order. However, this solution requires using a queue, which needs to take extra space. 

A better approach:
For a better approach without using extra space, we can observe the tree structure. Note that for each problem the tree in a perfect binary tree, which means that each node must have its left and right children. It indicates that all nodes except for the last node in each level has its next right node. So for each node has left child, root.left -> root.right; For each node root.right != null && root.next != null , root.right.next = root.next.left.

Code (Java):

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        if (root.left != null) {
            root.left.next = root.right;
        }
        
        if (root.next != null && root.next.left != null) {
            root.right.next = root.next.left;
        }
        
        connect(root.left);
        connect(root.right);
    }
}

Summary:
This problem is very tricky but if figure out the process of connecting nodes, it becomes very simple.

Update on 2/8/16:
Constant space solution:

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        TreeLinkNode curr = root;
        
        while (curr != null && curr.left != null && curr.right != null) {
            TreeLinkNode p = curr;
            while (p != null) {
                if (p.left != null) {
                    p.left.next = p.right;
                }
            
                if (p.right != null && p.next != null) {
                    p.right.next = p.next.left;
                }
                
                p = p.next;
            }
            
            curr = curr.left;
        }
    }
}

Leetcode: Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Understand the problem:
The main difference between the BST I is it requires to output all unique BSTs. So we can use recursion solution.


Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; left = null; right = null; }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return generateTreesHelper(1, n);
    }
    
    private List<TreeNode> generateTreesHelper(int start, int end) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        
        if (start > end) {
            result.add(null);
            return result;
        }
        
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = generateTreesHelper(start, i - 1);
            List<TreeNode> right = generateTreesHelper(i + 1, end);
            
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    result.add(root);
                }
            }
        }
        
        return result;
    }
}

Leetcode: Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,

Given n = 3, there are a total of 5 unique BST's. 

 1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Understand the problem:
The problem gives an integer n, asks for how many structurally unique BSTs that stores value 1 .. n available? 

Solution:
We use DP to solve this problem:
1. Definition: dp[i] means for integer i, how many unique BST's available.
2. Transit Function: dp[i]

For n = 2, dp[2] = dp[0] * dp[1]  // 1 as root 
                          + dp[1] * dp[0] // 2 as root

For n = 3, dp[3] =  dp[0] * dp[2]            // 1 as root
                          +  dp[1] * dp[1]           // 2 as root
                          +  dp[2] * dp[0]           // 3 as root

dp[i] = sum of dp[k] * dp[i - k - 1]; 0 <= k < i

3. Initial state dp[0] = 1; // Mean empty
                      dp[1] = 1; // 1 as root
4. Final state dp[n]

Code (Java):

public class Solution {
    public int numTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        
        return dp[n];
    }
}

A Recursive Approach:

public class Solution {
    public int numTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        
        return numTreesHelper(1, n);
    }
    
    private int numTreesHelper(int start, int end) {
        if (start >= end) {
            return 1;
        }
        
        int totalSum = 0;
        for (int i = start; i <= end; i++) {
            totalSum += numTreesHelper(start, i - 1) * numTreesHelper(i + 1, end);
        }
        
        return totalSum;
    }
}

Summary:
The take-away message for DP problem is the four steps approach. 
1. Define a DP array or matrix.
2. Figure out the transit functions.
3. Handle the initial state
4. Figure out the final state

Leetcode: Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?


Understand the problem:
As described in the problem, two elements of a BST are swapped by mistake. Recover the tree without changing its structure. There are two requirements in the problem. The first is we cannot change the structure of the tree. The second is do it in-place.


Solution:
If a binary tree is a BST, its inorder traversal should be in ascending order. We may use this property to solve this problem. Consider the following case:
For the inorder traversal list 123456, if 2 and 6 are swapped, the list becomes
163452. So when we scan the list, our goal is to mark the two swapped numbers and swap them back. So we can use two pointers, p and q. We compare the current value with the previous one, so when we see the first descending value, which is 3, the p pointer points to the previous node before 3, which is 6. When the next time we see the descending order again, which is 2, we use q pointer points to 2. Then we can swap the two numbers. 

Do we consider all the case? Actually there is still a case we did not consider. For the two numbers in adjacent, e.g. 123456, where 34 are swapped, so now it is 124356. The first time it encounters a descending order is at 3, where we point p to 4, the one before 3, then there is no other descending later. So where is q? So we should point q to this current position. 

Code (Java): 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode p,q;
    TreeNode prev = null;
    public void recoverTree(TreeNode root) {
        
        inOrderTraversal(root);
        
        int temp = p.val;
        p.val = q.val;
        q.val = temp;
    }
    
    private void inOrderTraversal(TreeNode root) {
        if (root == null) return;
        inOrderTraversal(root.left);
        
        if (prev != null && root.val < prev.val) {
            if (p == null) {
                p = prev;
                q = root;
            } else {
                q = root;
            }
        }
        prev = root;
        inOrderTraversal(root.right);
    }
}

Summary:
The problem looks tricky at the first glance. But at least you know the inorder traversal in ascending order for BST, the problem will become doable. The crux of this problem is to consider the two cases where swapped nodes are adjacent or not, and use two pointers pointing to the two nodes.   

Leetcode: Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Understand the problem:

The problem asks for checking if two trees are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value.  

Recursive Solution:

Note that for two trees are identical, both each node and the tree structures should be the same. So for each node, we first check if two node values are the same. Then we check both nodes have the same structure for left child and right child. We recursively repeat this process until we traversed all nodes of the tree.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return isSame(p, q);
    }
    
    private boolean isSame(TreeNode p, TreeNode q) {
        if (p == null) return q == null;
        if (q == null) return false;
        
        if (p.val != q.val) return false;
        
        if (isSame(p.left, q.left) == false) return false;
        if (isSame(p.right, q.right) == false) return false;
        
        return true;
    }
} 

Iterative Solution:
The iterative solution still utilized queues. However, if we follow the previous BFS way using a queue, we will falsely consider 1,2 and 1,#,2 as the same tree. Why? Because we don't allow null in the queue. If we allow null in the queue, the problem will be much easier. 
We maintain a queue for each tree respectively. We dequeue a node from each tree, and check if both are null, we pop a new node. If either is a null, we return false. If both are not null and with different value, we return false as well. Then we add its left and right child into the queue at last.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        
        Queue<TreeNode> lQueue = new LinkedList<TreeNode>();
        Queue<TreeNode> rQueue = new LinkedList<TreeNode>();
        
        lQueue.offer(p);
        rQueue.offer(q);
        if (lQueue.isEmpty() || rQueue.isEmpty()) return false;
        
        while (!lQueue.isEmpty() && !rQueue.isEmpty()) {
            TreeNode lCurr = lQueue.poll();
            TreeNode rCurr = rQueue.poll();
            
            if (lCurr == null && rCurr == null) continue;
            if (lCurr == null || rCurr == null) return false;
            
            if (lCurr.val != rCurr.val) return false;
            
            lQueue.offer(lCurr.left);
            lQueue.offer(lCurr.right);
            rQueue.offer(rCurr.left);
            rQueue.offer(rCurr.right);
        }
        
        
        return true;
    }
} 

Summary:
This question and the symmetric tree is the same kind of question. The recursive solution is very neat, but different from traditional DFS solution. The iterative solution using queue is a bit of tricky because we allow enqueue null into the queue, and utilized the null elements to check if the queue is the same. Be careful this idea. 

Leetcode: Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

Understand the problem:
The problem asks for checking if a tree is a mirror of itself, i.e, symmetric around its center. 
We can take several examples to show the problem:
Besides the  two examples shown above, 
An empty is symmetric. 
A tree with only 1 node is symmetric.
     1
    /  \
  3   4
is not symmetric.

Recursive Solution:
It is not hard to find that if a tree is symmetric, its inorder traversal list should be symmetric as well. For instance, for the first example, its inorder traversal is 3,2,4,1,4,2,3. Since the list is symmetric, the tree is symmetric as well.
For the second example, its inorder traversal is 2,3,1,2,3, which is not symmetric. 

So one straight-forward solution is to traverse the tree in-order ,save it to an array list. Then check the array list is symmetric. 

Wrong Answer:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        
        ArrayList<Integer> result = new ArrayList<Integer>();    
        inOrderTraversal(root, result);
        
        return isSymmetricArray(result);
    }
    
    private void inOrderTraversal(TreeNode root, ArrayList<Integer> result) {
        if (root == null) return;
        
        inOrderTraversal(root.left, result);
        result.add(root.val);
        inOrderTraversal(root.right, result);
    }
    
    private boolean isSymmetricArray(ArrayList<Integer> result) {
        int start = 0;
        int end = result.size() - 1;
        while (start < end) {
            if (result.get(start) != result.get(end)) return false;
            start++;
            end--;
        }
        return true;
    }
}

The code itself has nothing wrong, but the inorder traversal will result in the following wrong answer:

Input:	{1,2,3,3,#,2,#}
Output:	true
Expected:	false

Correct Solution:
So we must come out another solution. For a symmetric tree, the left child and right child of the root must be equal. Then for those two nodes, the left node's left child must be equal to the right node's right child; the left node's right child must be equal to the right node's left child. Then we recursively repeats those process until both nodes are null.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        
        return isSymmetric(root.left, root.right);
    }
    
    private boolean isSymmetric(TreeNode a, TreeNode b) {
        if (a == null) return b == null;
        else if (b == null) return false;
        
        if (a.val != b.val) return false;
        
        if (isSymmetric(a.left, b.right) == false) return false;
        if (isSymmetric(a.right, b.left) == false) return false;
        
        return true;
    }
}

Iterative Solution:
The iterative solution could borrow the idea of BFS, so we still use a queue to store intermediate results. Instead of using a queue, we used two queues, the left queue stores the left children, while the right queue stores the right children. We start from the root node, and enqueue its left and right child into the right and right queue, respectively, if left and right child existed. Then like the BFS, we dequeue two elements from the left and right queue each, and check if it is equal. If not, return false. Then we enqueue the left node's left child and right node's right child into the corresponding queue. And we enqueue left node's right child and right node's left child into the queue. We repeat this process until the queues are empty. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        
        Queue<TreeNode> lQueue = new LinkedList<TreeNode>();
        Queue<TreeNode> rQueue = new LinkedList<TreeNode>();
        
        if (root.left != null) lQueue.offer(root.left);
        if (root.right != null) rQueue.offer(root.right);
        
        while (!lQueue.isEmpty() || !rQueue.isEmpty()) {
            int size = Math.max(lQueue.size(), rQueue.size());
            for (int i = 0; i < size; i++) {
                if (lQueue.isEmpty() || rQueue.isEmpty()) return false;
                
                TreeNode a = lQueue.poll();
                TreeNode b = rQueue.poll();
                
                if (a.val != b.val) return false;
                
                if (a.left != null) lQueue.offer(a.left);
                if (b.right != null) rQueue.offer(b.right);
                if (a.right != null) rQueue.offer(a.right);
                if (b.left != null) lQueue.offer(b.left);
            }
        }
        
        return true;
    }
}

Summary:
The crux of the problem is to know how to determine if a tree is symmetric. If you know to compare two nodes' left and right children respectively, the problem becomes quite easy. An error-prone approach was showed. The mainly reason to come out that approach is to categorize a question into either BFS or DFS. Analogy is definitely helpful, but it is more important to go back the nature of the problem, and analyze what the problem asks for on earth. So be very careful about understanding the problem and deducing your solution.


Update on 10/7/14:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        Queue lQueue = new LinkedList();
        Queue rQueue = new LinkedList();
        
        lQueue.offer(root);
        rQueue.offer(root);
        
        while (!lQueue.isEmpty() && !rQueue.isEmpty()) {
            TreeNode curLeft = lQueue.poll();
            TreeNode curRight = rQueue.poll();
            if (curLeft.val != curRight.val) {
                return false;
            }
            
            if (curLeft.left != null) {
                lQueue.offer(curLeft.left);
            }
            
            if (curRight.right != null) {
                rQueue.offer(curRight.right);
            }
            
            if (curLeft.right != null) {
                rQueue.offer(curLeft.right);
            }
            
            if (curRight.left != null) {
                lQueue.offer(curRight.left);
            }
        }
        
        if (!lQueue.isEmpty() || !rQueue.isEmpty()) {
            return false;
        } else {
            return true;
        }
        
    }
}

Update on 4/14/15:
Iterative solution with allowing to add null into the queue.

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        Queue<TreeNode> lQueue = new LinkedList<TreeNode>();
        Queue<TreeNode> rQueue = new LinkedList<TreeNode>();
        
        lQueue.offer(root.left);
        rQueue.offer(root.right);
        
        while (!lQueue.isEmpty()) {
            TreeNode a = lQueue.poll();
            TreeNode b = rQueue.poll();
            
            if (a == null && b != null) {
                return false;
            }
            
            if (b == null && a != null) {
                return false;
            }
            
            if (a != null && b != null && a.val != b.val) {
                return false;
            }
            
            if (a != null) {
                lQueue.offer(a.left);
                lQueue.offer(a.right);
            }
            
            if (b != null) {
                rQueue.offer(b.right);
                rQueue.offer(b.left);
            }
        }
        
        return true;
    }
}

Leetcode: Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Understand the Problem:
The problem can be still categorized into BFS problem. The only difference between the regular BFS is it traversed the tree in Zigzag order. 

Recursive Solution:
We can still solve this problem using the regular BFS solution. However, for the even level, we store the nodes at reverse order. At the odd level, we store at the forward order. Then there is no difference between regular BFS and zigZag BFS.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        zigzagLevelOrder(root, result, 1);
        
        return result;
    }
    
    private void zigzagLevelOrder(TreeNode root, ArrayList<ArrayList<Integer>> result, int level) {
        if (root == null) return;
        
        if (result.size() < level) {
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            if ((level % 2) == 1) {
                levelList.add(root.val);
            } else {
                levelList.add(0, root.val);
            }
            result.add(levelList);
        } else {
            if ((level % 2) == 1) {
                result.get(level - 1).add(root.val);
            } else {
                result.get(level - 1).add(0, root.val);
            }
        }
        
        zigzagLevelOrder(root.left, result, level + 1);
        zigzagLevelOrder(root.right, result, level + 1);
    }
}

Discussion:
The time complexity for the recursive solution is still O(n^2) since inserting the node at head in the even levels takes O(n) time instead of O(1). 

Iterative Solution:
The iterative solution is very similar to the iterative BFS solution. There are two major difference in order do address this zigzag BFS. One is to save the level information, because we wanna store the node in backward order for even levels. Second, for the even level, we may still insert the nodes at head, as the recursive solution. Or we may employ a stack, and for the dequeued elements from the queue, we push into the stack. At last we pop all elements and append to the array list.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        int level = 0;
        
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            level++;
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            Stack<Integer> levelStack = new Stack<Integer>();
            
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if (level % 2 == 1) {
                    levelList.add(curr.val);
                } else {
                    levelStack.push(curr.val);
                }
                
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            
            // for even level, dump the elments from the stack to the arraylist
            if (level % 2 == 0) {
                while (!levelStack.isEmpty()) {
                    levelList.add(levelStack.pop());
                }
            }
            result.add(levelList);
        }
        
        return result;
    }
}

Discussion:
Since pushing and popping an element from the stack takes O(1) time, the overall time complexity is O(n). For the space complexity, since we employed a queue and stack to store the intermediate result, it takes space of O(n) + O(n) = O(n). So the space complexity is still O(n).

Summary:
So far you should be very familiar with all DFS and BFS traversal problems. The recursive solutions are straight-forward, but tricky to understand every detail. Be familiar with the iterative solution, and how queue, stack and pointers are used.

Update on 9/30/14:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> levelList = new ArrayList<Integer>();
            if (result.size() % 2 == 0) {
                for (int i = 0; i < size; i++) {
                    TreeNode curr = queue.poll();
                    levelList.add(curr.val);
                    
                    if (curr.left != null) {
                        queue.offer(curr.left);
                    }
                    
                    if (curr.right != null) {
                        queue.offer(curr.right);
                    }
                }
            } else {
                Stack<Integer> stack = new Stack<Integer>();
                for (int i = 0; i < size; i++) {
                    TreeNode curr = queue.poll();
                    stack.push(curr.val);
                    
                    if (curr.left != null) {
                        queue.offer(curr.left);
                    }
                    
                    if (curr.right != null) {
                        queue.offer(curr.right);
                    }
                }
                
                while(!stack.isEmpty()) {
                    levelList.add(stack.pop());
                }
            }
            result.add(levelList);
        }
        
        return result;
    }
}

Leetcode: Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Understand the problem:

The problem asks for traverse the binary tree in order. The mainly difference between the BFS is it asks for returning the result bottom-up.

Naive Solution:

One native solution is to still use the pre-order traversal of the tree, and save the level, like how we solved the BFS problem recursively. The major difference is instead of appending the list of each level, we add them at front of the result list, and move others forward. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        levelOrderBottom(root, result, 1);
        
        return result;
    }
    
    private void levelOrderBottom(TreeNode root, ArrayList<ArrayList>Integer>> result, int level) {
        if (root == null) return;
        
        if (result.size() < level) {
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            levelList.add(root.val);
            result.add(0, levelList);
        } else {
            result.get(result.size() - level).add(root.val);
        }
        
        levelOrderBottom(root.left, result, level + 1);
        levelOrderBottom(root.right, result, level + 1);
    }
}

Discussion:
Now let's analyze the complexity. Traversing all nodes of the tree takes O(n) time. However, adding the level list at the beginning of the result list and moving the rest behind takes O(n) time as well. So the overall time complexity is O(n^2).

A Better Solution:
Now that we know the time complexity is O(n^2), can we traverse the tree bottom-up, then append it to the array will takes only O(1) time thus the overall time complexity would be O(n). So far I was unabA Better Solution:
Now that we know the time complexity is O(n^2), can we traverse the tree bottom-up, then append it to the array will takes only O(1) time thus the overall time complexity would be O(n). 

So far I was unable to find a method to traverse the tree in level order bottom-up. It is hard to address the following tree
      1
     /  \
   2   3
        /  \
      15  7
If do the post-order traverse, it will start from 2 instead of 15. 

Iterative Solution:
The iterative solution for BFS is to use a queue. The idea is for each node, we enqueue all its left and right children into the queue, and dequeue all of them in next level. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                levelList.add(curr.val);
                
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            result.add(0, levelList);
        }                      
        return result;
    }
} 

Summary:
Note the iterative solution of the BFS, be very familiar with the details. In addition, one possible O(n) solution for the bottom-up traversal is to do the top-down traversal first and get the final result list. Then reverse the list in-place. Since reversing the list takes O(n) time as well, the overall time complexity is still O(n). 

Leetcode: Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Understand of the problem:
The problem asks for finding the maximum depth of a binary tree. The maximum depth is defined as the number of nodes along the longest path from the root down to the farthest leaf node. 

Recursive Solution:
The idea is still using pre-order traversal. We keep tracking of the depth of each node, and if the node is a leaf, we compare its depth with the maximum depth, and update the maximum depth, if needed. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int max = Integer.MIN_VALUE;
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        maxDepth(root, 0);
        
        return max;
    }
    
    private void maxDepth(TreeNode root, int depth) {
        if (root == null) return;
        
        depth++;
        
        // check if it is leaf
        if (root.left == null && root.right == null && depth > max) {
            max = depth;
        }
        
        maxDepth(root.left, depth);
        maxDepth(root.right, depth);
    }
}

Post-order Traversal Solution:
So far I think we have been very familiar with the pre-order traversal. For this problem, we can also do the post-order traversal of the binary tree, i.e, traverse from bottom-up. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        return Math.max(left, right) + 1;
    }
}

Post-order Iterative Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int max = 0;
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> depthStack = new Stack<Integer>();
        
        TreeNode prev = null;
        nodeStack.push(root);
        depthStack.push(1);
        
        while (!nodeStack.empty()) {
            TreeNode curr = nodeStack.peek();
            int depth = depthStack.peek();
            
            if (prev == null || curr == prev.left || curr == prev.right) {
                if (curr.left != null) {
                    nodeStack.push(curr.left);
                    depthStack.push(depth + 1);
                } else if (curr.right != null) {
                    nodeStack.push(curr.right);
                    depthStack.push(depth + 1);
                } else {
                    nodeStack.pop();
                    depthStack.pop();
                    if (depth > max) max = depth;
                }
            } else if (prev == curr.left) {
                if (curr.right != null) {
                    nodeStack.push(curr.right);
                    depthStack.push(depth + 1);
                } else {
                    nodeStack.pop();
                    depthStack.pop();
                    if (depth > max) max = depth;
                }
            } else if (prev == curr.right) {
                nodeStack.pop();
                depthStack.pop();
                if (depth > max) max = depth;
            }
            
            prev = curr;
        }
        return max;
    }
}

Summary:
The problem itself is very simple, but do be familiar with the post-order traversal. Especially be careful about the return value and how it works. 

Update on 9/30/14:
DFS solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int max = 0;
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        maxDepthHelper(root, 0);
        
        return max;
    }
    
    private void maxDepthHelper(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        
        depth++;
        
        if (root.left == null && root.right == null) {
            if (depth > max) {
                max = depth;
            }
            return;
        }
        
        maxDepthHelper(root.left, depth);
        maxDepthHelper(root.right, depth);
    }
}

Divide-and-Conquer

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        
        if (root == null) {
            return 0;
        }
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        return Math.max(left, right) + 1;
    }
}