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

Example 1:

Input:

    2
   / \
  1   3

Output:
 true

Example 2:

    5
   / \
  1   4
     / \
    3   6

Output:
 false

Explanation:
 The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

Thoughts:

1. Inorder traversal + checking ascending property in serialized array
2. Improving 1 by only recording the prev node
3. Iteratively defining the left and right bound of the node
4. Iterative Traversal (Generic to solve other problems such as Binary Tree Inorder Traversal, Kth Smallest in BST and Validate BST

Code 2:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode * prev = NULL;
        return isValidBST(root, prev);
    }
private:
    bool isValidBST(TreeNode * root, TreeNode* & prev){ // !!important to add "&" since the prev will be changed
    // as traversing down the BST  
        if(root == NULL) return true;
        if(!isValidBST(root->left, prev)) return false;
        if(prev != NULL && prev ->val >= root-> val) return false;
        prev = root;
        return isValidBST(root->right, prev);
    }
};

Code 3:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long min, long max){
        if(root == null) return true;
        if(root.val >= max || root.val <= min) return false;
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}

Code 4:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true; 
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()){
            // left 
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            // do
            if (pre!= null && pre.val >= root.val) return false;
            // record predecessor
            pre = root;
            // right
            root = root.right;
        }

        return true;
    }
}

Kth Smallest Element in a BST

 public int kthSmallest(TreeNode root, int k) {
     Stack<TreeNode> stack = new Stack<>();
     while(root != null || !stack.isEmpty()) {
         while(root != null) {
             stack.push(root);    
             root = root.left;   
         } 
         root = stack.pop();
         if(--k == 0) break;
         root = root.right;
     }
     return root.val;
 }

Binary Tree Inorder Traversal

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;

    }
    return list;
}