Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

/**

 * Your BSTIterator will be called like this:

 * BSTIterator i = new BSTIterator(root);

 * while (i.hasNext()) v[f()] = i.next();

 */

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

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

 * }

 */

/*

Every time, we call next(), we will traverse to find the left most TreeNode of the current node if existed. If the current node is null, then we pop out a node from the stack and return its value. The first time we call next(), it takes O(h) time, but the other TreeNode in the stack will take only O(1) time when call the next(). And there are h TreeNode in the stack. So the average time complexity will be O(1) and space complexity will be O(h).

hasNext() and next(): time:O(1), space:O(h)

*/

public class BSTIterator {

    public Stack<TreeNode> stack = new Stack<>();

    public TreeNode root;

    public BSTIterator(TreeNode root) {

        this.root = root;

    }

    /** @return whether we have a next smallest number */

    public boolean hasNext() {

        return root != null || !stack.isEmpty();

    }

    /** @return the next smallest number */

    public int next() {

        while (root != null) {

            stack.push(root);

            root = root.left;

        }

        root = stack.pop();

        TreeNode node = root;

        root = root.right;

        return node.val;

    }

}

Binary Tree Level Order Traversal

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

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

/*
BFS traversal, 
time:O(n), space:O(n)
*/

/**
 * 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<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ans.add(list);
        }
        return ans;
    }
}

Binary search tree minimum sum from root to leaf

Given a binary search tree, return the minimum sum from root to leaf.

/*
DFS,  search every path from root to leaf and compare the sum with the minimum sum. 

time:O(n), space:O(1)
*/

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}
public class Solution {
    public static int minPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int[] min = {Integer.MAX_VALUE};
        dfs(root, root.val, min);
        return min[0];
    }
    public static void dfs(TreeNode root, int sum, int[] min) {
        if (root.left == null && root.right == null) {
            min[0] = Math.min(min[0], sum);
            return;
        }
        if (root.left != null) {
            sum += root.left.val;
            dfs(root.left, sum, min);
            sum -= root.left.val;
        }
        if (root.right != null) {
            sum += root.right.val;
            dfs(root.right, sum, min);
            sum -= root.right.val;
        }
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(-2);
        TreeNode e = new TreeNode(-5);
        TreeNode f = new TreeNode(-4);
        a.left = b;
        a.right = c;
        b.left = d;
        c.left = e;
        c.right = f;
        int min = minPathSum(a);
        System.out.println(min);
    }
}

Subtree

You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Example

T2 is a subtree of T1 in the following case:

       1                3
      / \              / 
T1 = 2   3      T2 =  4
        /
       4

T2 isn't a subtree of T1 in the following case:

       1               3
      / \               \
T1 = 2   3       T2 =    4
        /
       4

/**
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

//time:O(mn), space:O(1)

public class Solution {
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        if (T2 == null) {
            return true;
        }
        if (T1 == null) {
            return false;
        }
        if (identical(T1, T2)) {
            return true;
        }
        if (isSubtree(T1.left, T2) || isSubtree(T1.right, T2)) {
            return true;
        }
        return false;
    }
    
    public boolean identical(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return root1 == root2;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return identical(root1.left, root2.left) && 
               identical(root1.right, root2.right);
    }
}

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.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

/*
DFS, recursion 
time:O(n), space:O(1)
*/

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            return p == q;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && 
               isSameTree(p.right, q.right);
    }
}