Lowest Common Ancestor of a Binary Search Tree

★★☆☆☆

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null && (root.val - p.val) * (root.val - q.val) > 0)
            root = (root.val > p.val)? root.left: root.right;
        return root;
    }
}

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.

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int botGet = root.val;
        if (root.val > target && root.left != null)
            botGet = closestValue(root.left, target);
        else if (root.val < target && root.right != null)
            botGet = closestValue(root.right, target);
        return Math.abs(botGet - target) < Math.abs(root.val - target)? botGet: root.val;
    }
}

Validate Binary Search Tree

★★☆☆☆

// solution 1: recursive
public boolean isValidBST(TreeNode root) {
    return isValidNode(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidNode(TreeNode node, long minVal, long maxVal) {
    if (node == null) return true;
    if (node.val <= minVal || node.val >= maxVal) return false;
    return isValidNode(node.left, minVal, node.val) && isValidNode(node.right, node.val, maxVal);
}
// solution 2: iterative
public boolean isValidBST(TreeNode root) {
    return (root == null)? true: helper(root, null) != null;
}
public TreeNode helper(TreeNode node, TreeNode pre) {
    if (node == null) return pre;
    if (node.left != null) {
        pre = helper(node.left, pre);
        if (pre == null) return null;
    }
    if (pre != null && node.val <= pre.val) return null;
    return helper(node.right, node);
}
// solution 3: morris traversal
public boolean isValidBST(TreeNode root) {
    boolean meetfirst = false;
    int preVal = 0;
    while (root != null) {
        if (root.left == null) {
            if (!meetfirst) {
                preVal = root.val;
                meetfirst = true;
            }
            else {
                if (preVal >= root.val) return false;
            }
            preVal = root.val;
            root = root.right;
        }
        else {
            TreeNode preNode = root.left;
            while (preNode.right != null && preNode.right != root)
                preNode = preNode.right;//find node previous to root
            if (preNode.right == null) {
                preNode.right = root;//morris connection!
                root = root.left;
            }
            else {//should always satisfy preNode.right == root
                preNode.right = null;//recover the tree structure
                if (!meetfirst) {
                    preVal = root.val;
                    meetfirst = true;
                }
                else {
                    if (preVal >= root.val) return false;
                }
                preVal = root.val;
                root = root.right;
            }
        }
    }
    return true;
}