[LeetCode] 938. Range Sum of BST

 Problem : https://leetcode.com/problems/range-sum-of-bst/

Use BST property to trim branches outside of the range.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        // left subtree and current node are out of the range
        if (root.val < low)  return rangeSumBST(root.right, low, high);
        // right subtree and current node are out of the range
        if (root.val > high) return rangeSumBST(root.left, low, high);
        // current node is inside of the range
        return rangeSumBST(root.left, low, high) + root.val + rangeSumBST(root.right, low, high);
    }
}

[LeetCode] 450. Delete Node in a BST

 Problem : https://leetcode.com/problems/delete-node-in-a-bst/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) { 
        if (root == null) {
            return root;
        }
        
        // delete node from left sub-tree
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        
        // delete node from right sub-tree
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
        
        // root.val == key
        if (root.left == null) {
            return root.right;
        }
        
        if (root.right == null) {
            return root.left;
        }
        
        // use right node as the new root
        TreeNode newRoot = root.right;
        
        // Because all nodes in right sub-tree are larger than current root node,
        // and left child is less than current root node, 
        // then the left child must be the smallest value comparing to the right sub-tree.
        // Attach current left child to the most left node of the right sub-tree.
        TreeNode p = root.right;
        while (p.left != null) {
            p = p.left;
        }
        
        p.left = root.left;
        
        return newRoot;
    }
}

[LeetCode] 333. Largest BST Subtree

 Problem : https://leetcode.com/problems/largest-bst-subtree/

To form a BST, the left sub-tree and right sub-tree are also need to be BST.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        self.result = 1
        
        def postorder(node):
            if node.left and node.right:
                lmx, lmi, ltotal = postorder(node.left)
                rmx, rmi, rtotal = postorder(node.right)
                
                if ltotal < 0 or rtotal < 0:
                    return lmx, lmi, -1
                
                if node.val <= lmx:
                    return lmx, lmi, -1
                
                if node.val >= rmi:
                    return rmx, rmi, -1
                
                
                self.result = max(self.result, 1 + ltotal + rtotal)
                
                return rmx, lmi, 1 + ltotal + rtotal
            
            if node.left:
                lmx, lmi, ltotal = postorder(node.left)
                
                if ltotal < 0 :
                    return lmx, lmi, -1
                
                if node.val <= lmx:
                    return lmx, lmi, -1
                
                self.result = max(self.result, 1 + ltotal)
                return node.val, lmi, 1 + ltotal
            
            if node.right:
                rmx, rmi, rtotal = postorder(node.right)
                
                if rtotal < 0:
                    return rmx, rmi, -1
                
                if node.val >= rmi:
                    return rmx, rmi, -1
                
                self.result = max(self.result, 1 + rtotal)
                
                return rmx, node.val, 1 + rtotal
            
            return node.val, node.val, 1
        
        postorder(root)
        
        return self.result

[LeetCode] 1586. Binary Search Tree Iterator II

 Problem : https://leetcode.com/problems/binary-search-tree-iterator-ii/

Use another stack to save the previous nodes while iterating through in-order traversal.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self.pre = []
        
        while root:
            tmp = root.left
            root.left = None
            self.stack.append(root)
            root = tmp
            

    def hasNext(self) -> bool:
        return len(self.stack) > 0
        
    def next(self) -> int:
        node = self.stack.pop()
        self.pre.append(node)
        
        if node.right:
            tmp = node.right
            node.right = None
            
            node = tmp
            
            while node:
                tmp = node.left
                node.left = None
                self.stack.append(node)
                node = tmp
        
        return self.pre[-1].val
    
    def hasPrev(self) -> bool:
        return len(self.pre) >= 2
        

    def prev(self) -> int:
        node = self.pre.pop()
        self.stack.append(node)
        return self.pre[-1].val


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.hasNext()
# param_2 = obj.next()
# param_3 = obj.hasPrev()
# param_4 = obj.prev()

[LeetCode] 285. Inorder Successor in BST

 Problem : https://leetcode.com/problems/inorder-successor-in-bst/

The recursive approach:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        self.pre = None
        
        def inorder(node):
            if node:
                tmp = inorder(node.left)
                if tmp: return tmp
                
                if self.pre == p:
                    return node
                
                self.pre = node
                
                tmp = inorder(node.right)
                if tmp: return tmp
        
        return inorder(root)

The iterative approach:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        pre = None
        stack = [root]
        
        while stack:
            node = stack[-1]
            
            while node.left:
                stack.append(node.left)
                left = node.left
                node.left = None
                node = left
            
            node = stack.pop()
            if pre == p: 
                return node
            
            pre = node
            
            if node.right:
                stack.append(node.right)
                node.right = None

However the previous 2 approaches do not leverage BST properties.

We can safely discard the left sub-tree, if root.val <= p.val

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        
        result = None
        
        while root:
            if p.val >= root.val:
                root = root.right
            else:
                result = root
                root = root.left
    
        return result

[LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree

Problem : https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Let p be smaller than q.

If root > q,  p and q's lowest common ancestor is in the left sub-tree.

If root < p,  p and q's lowest common ancestor is in the right sub-tree.

Otherwise, we find the lowest common ancestor of p and q.

Time complexity = O ( N )

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        if not root:
            return root
        
        # make sure p < q
        if p.val > q.val:
            p, q = q, p
        
        if root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        
        if root.val < p.val:
            return self.lowestCommonAncestor(root.right, p, q)

        return root

[LeetCode] 230. Kth Smallest Element in a BST

Problem: https://leetcode.com/problems/kth-smallest-element-in-a-bst/

In-order traverse the BST until collected K elements.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        
        gen = inorder(root)
        return [next(gen) for _ in range(k)][-1]

Edited on 06/06/2021. Update the inorder traversal approach.

[LeetCode] 108. Convert Sorted Array to Binary Search Tree

Problem : https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Use the middle number as the parent node and recursively build the left and right sub-tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        
        def helper(left, right):
            if left >= right:
                return None
            
            mid = left + (right - left) // 2
            return TreeNode(nums[mid], helper(left, mid), helper(mid+1, right))
        
        return helper(0, len(nums))

Edited on 07/26/2021. Tidy the code.

[LeetCode] 98. Validate Binary Search Tree

Problem : https://leetcode.com/problems/validate-binary-search-tree/

In-order traversing a BST generates an ascending sequence.  Use this BST characteristic to valid the given BST.

Time Complexity = O ( N ).   N = total nodes of the BST.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        
        def inorder(node, pre_val):
            if node:
                result = inorder(node.left, pre_val)
                
                if not result[1]:
                    return (pre_val, False)
                
                pre_val = result[0]
                
                if pre_val != None and pre_val >= node.val:
                    return (pre_val, False)
                
                pre_val = node.val
                
                result = inorder(node.right, pre_val)
                
                if not result[1]:
                    return (pre_val, False)
                    
                return result
            else:
                return (pre_val, True)
            
        
        return inorder(root, None)[1]

For a valid BST, values on left child tree must be in range [-2**31, root.val) and values on right child tree must be in range (root.val, 2**31-1]

Check if values in left / right sub-trees fall into the valid range.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root: return True
        
        def inorder(node, mi, mx):
            if node.left:
                if not inorder(node.left, mi, node.val - 1):
                    return False
            
            if mx != None and node.val > mx:
                return False
            
            if mi != None and node.val < mi:
                return False
            
            if node.right:
                return inorder(node.right, node.val + 1, mx)
            
            return True
        
        return inorder(root, None,  None)

[LeetCode] 95. Unique Binary Search Trees II

Problem : https://leetcode.com/problems/unique-binary-search-trees-ii/

In BST,  each node is larger than every nodes in its left sub-tree and smaller than every nodes in its right sub-tree.  We should use every valid integer as root node and create BST recursively.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        
        def helper(left, right):
            if left == right:
                return [TreeNode(val=left)]
            elif left > right:
                return [None]
            else:
                return [TreeNode(val=pivot, left=l, right=r) for pivot in range(left, right+1) for l in helper(left, pivot - 1) for r in helper(pivot+1, right)]

        return helper(1, n)

Edited on 09/02/2021. Update a simpler solution.