LeetCode Problem: Tree Topics

1. Smallest Subtree with all the Deepest Nodes

Given a binary tree rooted at root, the depth of each node is the shortest distance to the root. A node is deepest if it has the largest depth possible among any node in the entire tree. The subtree of a node is that node, plus the set of all descendants of that node. Return the node with the largest depth such that it contains all the deepest nodes in its subtree.

Here is the code to solve the problem:

public class SmallestSubtree {
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).node;
    }

    // Return the result of the subtree at this node.
    public Result dfs(TreeNode node) {
        if (node == null) return new Result(null, 0);
        Result L = dfs(node.left),
                R = dfs(node.right);
        if (L.dist > R.dist) return new Result(L.node, L.dist + 1);
        if (L.dist < R.dist) return new Result(R.node, R.dist + 1);
        return new Result(node, L.dist + 1);
    }
}

class Result {
    TreeNode node;
    int dist;

    Result(TreeNode n, int d) {
        node = n;
        dist = d;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

We should use DFS to solve this problem, and the process is like this:https://www.youtube.com/watch?v=iWf-DleqY9c

---

2. Symmetric Tree

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

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

But the following [1,2,2,null,3,null,3] is not:

  1
 / \
2   2
 \   \
 3    3

To solve this problem, we need to do pair comparisons recursively. For example, if we want to check whether the following array is symmetric, we need to use two pointers to traverse and compare pairs of values:

[1, 2, 3, 3, 2, 1]
⬆              ⬆

[1, 2, 3, 3, 2, 1]
    ⬆       ⬆

[1, 2, 3, 3, 2, 1]
       ⬆ ⬆

In this problem, we need to compare pairs of subtrees:

public class SymmetricTree {
    public boolean isSymmetric(TreeNode root) {
        // if root == null, it is symmetric
        // if root != null, we need to check w
        return root == null || check(root.left, root.right);
    }

    public boolean check(TreeNode left, TreeNode right) {
        if(left == null || right == null) {
            return left == right;
        }

        if(left.val != right.val) {
            return false;
        }

        return check(left.left, right.right) && check(left.right, right.left);

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

The process of the above code is like this:https://www.youtube.com/watch?v=DfoAOO0ZgPY

Using the same idea(two pointers, pair comparison), we can also check wether two trees are same tree or not.

---

3. 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.

Example 1:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

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


Example 2:
Input: [1,2,3,null,5,null,null]
Output: [1, 3, 5]
Explanation:

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

To solve this problem, we should use breadth-first search(BFS), and collect the rightmost elements at each level. We use a queue to do the search:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTreeRightSideView {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode currentNode = queue.remove();

                if(i == size - 1) {// the last node at each level
                    result.add(currentNode.val);
                }

                if(currentNode.left != null) {
                    queue.add(currentNode.left);
                }

                if(currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }
        }
        return result;

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

The process of the above code is like this:https://www.youtube.com/watch?v=8GJlxWrfveE

---

4. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Because the array is sorted, we can use the idea of binary search to solve this problem:

public class ConvertSortedArrayToBST {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }

        return dfs(nums, 0, nums.length - 1);
    }

    public TreeNode dfs(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = dfs(nums, left, mid - 1);
        node.right = dfs(nums, mid + 1, right);

        return node;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

The process of the above code is like this:https://www.youtube.com/watch?v=VeYo_oWsLVw

---