Leetcode: Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

Brute-force solution: O(n)
The most straight-forward solution is to do a in-order traversal of the BST. When we found the target node, we look for the smallest number greater than the node.

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }
        
        if (p == root) {
            return p.right;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode q = root;
        
        while (!stack.isEmpty() || q != null) {
            if (q != null) {
                stack.push(q);
                q = q.left;
            } else {
                TreeNode curr = stack.pop();
                q = curr.right;
                
                if (curr == p) {
                    if (curr.right != null) {
                        TreeNode m = curr.right;
                        while (m.left != null) {
                            m = m.left;
                        }
                        return m;
                        
                    } else if (!stack.isEmpty()){
                        return stack.pop();
                    }
                }
            }
        }
        
        return null;
    }
}

An O(h) Solution:
Since the given p node is a node in the BST (not just a value), we can directly start from the node.  There are two cases to consider:
1. If the p.right != null. Then the successor of p must be the minimum number of the right subtree.
2. If the p.right == null, then the successor of p must be the minimum number which is greater than p's value. We could start from root, if the value of the root is greater than the p.val. Then we go to the left subtree because we wanna try a smaller one. However we need to save this node because it is possible that the root.left would be smaller than the p.val. If the root's val is less than the p.val, then we simply go to the right subtree. 

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }
        
        if (p.right != null) {
            return findMin(p.right);
        }
        
        // Case 2: p.right == null
        TreeNode succ = null;
        TreeNode q = root;
        
        while (q != null) {
            if (q.val > p.val) {
                succ = q;
                q = q.left;
            } else if (q.val < p.val) {
                q = q.right;
            } else {
                break;
            }
        }
        
        return succ;
    }
    
    private TreeNode findMin(TreeNode root) {
        TreeNode p = root;
        
        while (p.left != null) {
            p = p.left;
        }
        
        return p;
    }
}

Leetcode: Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

• Given target value is a floating point.
• You may assume k is always valid, that is: k ≤ total nodes.
• You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

1. Consider implement these two helper functions:
   1. getPredecessor(N), which returns the next smaller node to N.
   2. getSuccessor(N), which returns the next larger node to N.
2. Try to assume that each node has a parent pointer, it makes the problem much easier.
3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
4. You would need two stacks to track the path in finding predecessor and successor node separately.

Brute-force solution:
The straight-forward solution would be to use a heap. We just treat the BST just as a usual array and do a in-order traverse. Then we compare the current element with the minimum element in the heap, the same as top k problem.

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private PriorityQueue<Integer> minPQ;
    private int count = 0;
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        minPQ = new PriorityQueue<Integer>(k);
        List<Integer> result = new ArrayList<Integer>();
        
        inorderTraverse(root, target, k);
        
        // Dump the pq into result list
        for (Integer elem : minPQ) {
            result.add(elem);
        }
        
        return result;
    }
    
    private void inorderTraverse(TreeNode root, double target, int k) {
        if (root == null) {
            return;
        }
        
        inorderTraverse(root.left, target, k);
        
        if (count < k) {
            minPQ.offer(root.val);
        } else {
            if (Math.abs((double) root.val - target) < Math.abs((double) minPQ.peek() - target)) {
                minPQ.poll();
                minPQ.offer(root.val);
            }
        }
        count++;
        
        inorderTraverse(root.right, target, k);
    }
}

Analysis:
The time complexity would be O(k + (n - k) logk). 
Space complexity is O(k).

A time linear 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> closestKValues(TreeNode root, double target, int k) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Stack<Integer> precedessor = new Stack<>();
        Stack<Integer> successor = new Stack<>();
        
        getPredecessor(root, target, precedessor);
        getSuccessor(root, target, successor);
        
        for (int i = 0; i < k; i++) {
            if (precedessor.isEmpty()) {
                result.add(successor.pop());
            } else if (successor.isEmpty()) {
                result.add(precedessor.pop());
            } else if (Math.abs((double) precedessor.peek() - target) < Math.abs((double) successor.peek() - target)) {
                result.add(precedessor.pop());
            } else {
                result.add(successor.pop());
            }
        }
        
        return result;
    }
    
    private void getPredecessor(TreeNode root, double target, Stack<Integer> precedessor) {
        if (root == null) {
            return;
        }
        
        getPredecessor(root.left, target, precedessor);
        
        if (root.val > target) {
            return;
        }
        
        precedessor.push(root.val);
        
        getPredecessor(root.right, target, precedessor);
    }
    
    private void getSuccessor(TreeNode root, double target, Stack<Integer> successor) {
        if (root == null) {
            return;
        }
        
        getSuccessor(root.right, target, successor);
        
        if (root.val <= target) {
            return;
        }
        
        successor.push(root.val);
        
        getSuccessor(root.left, target, successor);
    }
}

Update on 4/30/19: Time complexity O(k + logn)

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

public class Solution {
    /**
     * @param root: the given BST
     * @param target: the given target
     * @param k: the given k
     * @return: k values in the BST that are closest to the target
     */
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        // step 1: find the closet value and save the path
        Stack<TreeNode> lowerStack = new Stack<>();
        Stack<TreeNode> upperStack = new Stack<>();

        TreeNode p = root;
        while (p != null) {
            if (p.val < target) {
                lowerStack.push(p);
                p = p.right;
            } else {
                upperStack.push(p);
                p = p.left;
            }
        }

        for (int i = 0; i < k; i++) {
            if (lowerStack.isEmpty()) {
                TreeNode top = upperStack.pop();
                ans.add(top.val);
                goUpperNext(top.right, upperStack);
            
            } else if (upperStack.isEmpty()) {
                TreeNode top = lowerStack.pop();
                ans.add(top.val);
                goLowerNext(top.left, lowerStack);
            } else if (upperStack.peek().val - target <= target - lowerStack.peek().val) {
                TreeNode top = upperStack.pop();
                ans.add(top.val);
                goUpperNext(top.right, upperStack);
            } else if (upperStack.isEmpty() || target - lowerStack.peek().val < upperStack.peek().val - target) {
                TreeNode top = lowerStack.pop();
                ans.add(top.val);
                goLowerNext(top.left, lowerStack);
            }
        }

        return ans;
    }

    private void goUpperNext(TreeNode node, Stack<TreeNode> stack) {
        TreeNode p = node;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
    }

    private void goLowerNext(TreeNode node, Stack<TreeNode> stack) {
        TreeNode p = node;
        while (p != null) {
            stack.push(p);
            p = p.right;
        }
    }
}

Leetcode: Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private double min = Double.MAX_VALUE;
    private int ans = 0;
    public int closestValue(TreeNode root, double target) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        
        closestValueHelper(root, target);
        
        return ans;
    }
    
    private void closestValueHelper(TreeNode root, double target) {
        if (root == null) {
            return;
        }
        
        if (Math.abs((double) root.val - target) < min) {
            min = Math.abs((double) root.val - target);
            ans = root.val;
        }
        
        if (root.val > target) {
            closestValueHelper(root.left, target);
        } else if (root.val < target) {
            closestValueHelper(root.right, target);
        }
    }
}

Iterative 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 int closestValue(TreeNode root, double target) {
        if (root == null) {
            throw new NullPointerException("Tree must be non-empty");
        }
        
        int result = 0;
        double gap = Double.MAX_VALUE;
        
        while (root != null) {
            if (root.val == target) {
                return root.val;
            }
            
            double dist = Math.abs(root.val - target);
            if (dist < gap) {
                result = root.val;
                gap = dist;
            }
            
            if (target > root.val) {
                root = root.right;
            } else if (target < root.val) {
                root = root.left;
            }
        }
        return result;
    }
}

Leetcode: Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:
Could you do it using only constant space complexity?

Brute-force solution:
The idea to solve the problem is: a[0] must be the root of the BST. Then we start from index 1 and iterate until a number which is greater than root, mark as i. All the numbers less than i must be less than root, number greater than i must be greater than root. Then we can recursively validate the BST.

先复习一下BST，给定一个节点，其左子树的所有节点都小于该节点，右子树的所有节点都大于该节点；preorder序列是指在遍历该BST的时候，先记录根节点，再遍历左子树，然后遍历右子树；所以一个preorder序列有这样一个特点，左子树的序列必定都在右子树的序列之前；并且左子树的序列必定都小于根节点，右子树的序列都大于根节点；

根据上面的特点很容易通过递归的方式完成：

1. 如果序列只有一个元素，那么肯定是正确的，对应只有一个节点的树；
2. 如果多于一个元素，以当前节点为根节点；并从当前节点向后遍历，直到大于根节点的节点出现（或者到尾巴），那么根节点之后，该大节点之前的，是左子树；该大节点及之后的组成右子树；递归判断左右子树即可；
3. 那么什么时候一个序列肯定不是一个preorder序列呢？前面得到的右子树，如果在其中出现了比根节点还小的数，那么就可以直接返回false了；

Code (Java):

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) {
            return true;
        }
        
        return verifyPreorderHelper(preorder, 0, preorder.length - 1);
    }
    
    private boolean verifyPreorderHelper(int[] preorder, int lo, int hi) {
        if (lo >= hi) {
            return true;
        }
        
        int root = preorder[lo];
        int i = lo + 1;
        while (i <= hi && preorder[i] < root) {
            i++;
        }
        
        int j = i;
        while (j <= hi && preorder[j] > root) {
            j++;
        } 
        
        if (j <= hi) {
            return false;
        }
        
        return verifyPreorderHelper(preorder, lo + 1, i - 1) && 
               verifyPreorderHelper(preorder, i, hi);
    }
}

Analysis:
Time complexity O(n^2), space complexity O(1). 


Solution using two stacks:
http://segmentfault.com/a/1190000003874375

Use a stack to store the numbers less than num, and a list to store the numbers in an ascending order. If the in-order list descends, return false. 

Code (Java):

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) {
            return true;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        List<Integer> list = new ArrayList<>();
        
        for (int num : preorder) {
            if (!list.isEmpty() && num < list.get(list.size() - 1)) {
                return false;
            }
            
            while (!stack.isEmpty() && num > stack.peek()) {
                list.add(stack.pop());
            }
            
            stack.push(num);
        }
        
        return true;
    }
}

Solution using one stack:
Since the in-order list only stores the number in ascending order. We can use a variable to store only the last i.e max value. 

Code (Java):

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) {
            return true;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        int max = Integer.MIN_VALUE;
        
        for (int num : preorder) {
            if (num < max) {
                return false;
            }
            
            while (!stack.isEmpty() && num > stack.peek()) {
                max = stack.pop();
            }
            
            stack.push(num);
        }
        
        return true;
    }
}

A constant-space solution:

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) {
            return true;
        }
        
        int i = -1;
        int max = Integer.MIN_VALUE;
        
        for (int num : preorder) {
            if (num < max) {
                return false;
            }
            
            while (i >= 0 && num > preorder[i]) {
                max = preorder[i];
                i--;
            }
            
            i++;
            preorder[i] = num;
        }
        
        return true;
    }
}

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: Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

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

Understand the problem:
The problem asks for validating if a binary tree is a binary search tree. So we must first understand what is a BST? Basically, a BST is a binary tree where nodes are ordered in the following way:

• each node contains one key, also known as data
• the keys in the left subtree are less than the key in its parent node
• the keys in the right subtree are greater than the key in the parent node
• duplicated keys are not allowed.

Consequently, it is not hard to find that BST is defined in a recursive way. So we may use DFS to traverse the tree.

Solution:
Since the BST is defined as left children is less than the parent, while right children is greater than the parent. So we can in inorder traversal to traverse the tree. We use inorder traverse because it goes to left child first, then parent, then right child. They should be ordered in a ascending order, if it is a BST.

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 min = Integer.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        return inOrderTraverse(root);
    }
    
    public boolean inOrderTraverse(TreeNode node) {
        if (node == null) return true;
        
        if (inOrderTraverse(node.left) == false) return false;
        
        if (node.val > min) {
            min = node.val;
        } else return false;
        
        
        if (inOrderTraverse(node.right) == false) return false;
        
        return true;
    }
}

Another 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 min = Integer.MIN_VALUE;
    private boolean ret = true;
    
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        inOrderTraverse(root);
        return ret;
    }
    
    public void inOrderTraverse(TreeNode node) {
        if (node == null || ret == false) return;
        
        inOrderTraverse(node.left);
        
        if (node.val > min) {
            min = node.val;
        } else {
            ret = false;
            return;
        }
        
        inOrderTraverse(node.right);
    }
}

Discussion:
Both solution 1 and 2 are based on inorder traversal. In the first solution, the recursive function has a return value. Be careful about the recursive function with a return value. In t he second solution, it is more close to inorder traversal. Note that it needs to use a global variable to save the return value. 


Another solution:
Remember that the BST is left children is smaller than the key, while the right ones are greater. We can use this property to recursively validate that.

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 isValidBST(TreeNode root) {
        return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private boolean isBST(TreeNode node, int min, int max) {
        if (node == null) return true;
        
        if (node.val <= min || node.val >= max) {
            return false;
        }
        
        return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);
    }
}

Summary:
In this post, we learned how to validate a binary tree is a BST. For the tree related question, there are two major ways to consider, DFS and BFS. 

Update 10/28/14:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        
        int prev = Integer.MIN_VALUE;
        
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode curr = stack.pop();
                if (curr.val <= prev) {
                    return false;
                }
                
                prev = curr.val;
                
                p = curr.right;
            }
        }
        
        return true;
    }
}

Update on 2/16/15:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isBST(root, null, null);
    }
    
    private boolean isBST(TreeNode node, Integer min, Integer max) {
        if (node == null) return true;
        
        if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
            return false;
        }
        
        return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);
    }
}

Update on 4/30/19

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

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        // write your code here
        if (root == null) {
            return true;
        }

        ResultType ans = isValidBSTHelper(root);
        return ans.isBST;
    }

    private ResultType isValidBSTHelper(TreeNode root) {
        if (root == null) {
            return new ResultType(Integer.MIN_VALUE, Integer.MAX_VALUE, true);
        }

        ResultType left = isValidBSTHelper(root.left);
        ResultType right = isValidBSTHelper(root.right);
        
        if (!left.isBST || !right.isBST) {
            return new ResultType(0, 0, false);
        }
        
        if (root.left != null && root.val <= left.max) {
            return new ResultType(0, 0, false);
        }
        
        if (root.right != null && root.val >= right.min) {
            return new ResultType(0, 0, false);
        }

        int max = Math.max(root.val, right.max);
        int min = Math.min(root.val, left.min);

        return new ResultType(max, min, true);
    }
}

class ResultType {
    int max;
    int min;
    boolean isBST;

    public ResultType(int max, int min, boolean isBST) {
        this.max = max;
        this.min = min;
        this.isBST = isBST;
    }
}