These are some additional questions that are not covered in previous NineChap posts. Some questions are non-standard and difficult to solve, and some are not found in OJ websites. But these are real questions that has been asked during interviews.

Question list

1. Binary Search Tree find upper/lower bound

2. Implement iterator of Binary Search Tree

3. Binary Tree Serialize and Deserialize

4. Populating Next Right Pointers in Each Node

5. Populating Next Right Pointers in Each Node II - difficult

6. Symmetric Tree

7. Same Tree

Code

Binary Search Tree find upper/lower bound

Find the new post.

Implement iterator of Binary Search Tree

Find the new post.

Binary Tree Serialize and Deserialize

Find the new post.

Populating Next Right Pointers in Each Node

public void connect(TreeLinkNode root) {
    TreeLinkNode dummy = new TreeLinkNode(0);
    dummy.left = root;
    helper(dummy, root);
}

private void helper(TreeLinkNode parent, TreeLinkNode child) {
    if (child == null) {
        return;
    }
    if (child == parent.left) {
        child.next = parent.right;
    } else if (child == parent.right) {
        if (parent.next != null) {
            child.next = parent.next.left;
        }
    }
    helper(child, child.left);
    helper(child, child.right);
}

Populating Next Right Pointers in Each Node II

This is a very tricky variant of DFS where the left sub-tree is making use of right sub-tree. I did not solve it even at second time.

public void connect(TreeLinkNode root) {
    if (root == null) return;
    if (root.left == null && root.right == null) return;
    TreeLinkNode levelNext = root.next;
    TreeLinkNode lowerNext = null;
    while (levelNext != null && lowerNext == null) {
        if (levelNext.left != null) {
            lowerNext = levelNext.left;
            break;
        } else if (levelNext.right != null) {
            lowerNext = levelNext.right;
            break;
        } else {
            // if there is no child node of levelNext
            levelNext = levelNext.next;
        }
    }
    if (root.left == null) {
        root.right.next = lowerNext;
    } else if (root.right == null) {
        root.left.next = lowerNext;
    } else {
        root.left.next = root.right;
        root.right.next = lowerNext;
    }
    connect(root.right);
    connect(root.left);
}

Symmetric Tree

public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    return mirror(root.left, root.right);
}

private boolean mirror(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null) {
        return false;
    }
    return (left.val == right.val) 
        & mirror(left.left, right.right)
        & mirror(left.right, right.left);
}

Same Tree

public boolean isSameTree(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null) {
        return false;
    }
    return (left.val == right.val) 
        & isSameTree(left.left, right.left)
        & isSameTree(left.right, right.right);
}