BST

99. Recover Binary Search Tree

1. x, y are nodes to swap, pre is previous node

Iterative

def recoverTree(self, root: TreeNode) -> None:
    x = y = pre = None
    stack = []
    node = root
    
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        
         # 先遇到 x or y, pre代表的點不一樣
        if pre and pre.val > node.val:
            y = node
            if x == None:
                x = pre
            else:
                break
        pre = node
        node = node.right
            
    x.val, y.val = y.val, x.val

Recursive

def recoverTree(self, root: TreeNode) -> None:
    def find_swap(node):
        nonlocal x, y, pre
        if not node: return
        find_swap(node.left)
        
        if pre and pre.val > node.val:
            y = node
            # first swap point
            if x == None:
                x = pre
            # second swap point
            else:
                return
        pre = node
        find_swap(node.right)
     
    x = y = pre = None
    find_swap(root)    
    x.val, y.val = y.val, x.val

Morris

def recoverTree(self, root: TreeNode) -> None:
    def findPredecessor(node):
        pre = node.left
        while pre.right and pre.right != node:
            pre = pre.right
        return pre
    
    cur = root
    x = y = pre = None
    while cur:
        if cur.left:
            predecessor = findPredecessor(cur)
            if not predecessor.right:
                predecessor.right = cur
                cur = cur.left
            else:
                if pre and pre.val > cur.val:
                    y = cur
                    if not x:
                        x = pre
                # will casue cycle if break the loop
                #    else:
                #        break
            
                predecessor.right = None
                pre = cur
                cur = cur.right
        else:
            if pre and pre.val > cur.val:
                y = cur
                if not x:
                    x = pre
                # will casue cycle if break the loop
                #else:
                #    break
             
            pre = cur
            cur = cur.right
            
    x.val, y.val = y.val, x.val
    

450 Delete Node

• 1 child, 2 child situation

• 2 child => find min in right child

• delete min in right child

def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
    if not root: return None
    
    if root.val < key:
        root.right = self.deleteNode(root.right, key)
        return root
    
    elif root.val > key:
        root.left = self.deleteNode(root.left, key)
        return root
    
    else:
        if not root.left and not root.right:
            return None
        elif not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            min_val = self.findMin(root.right)
            root.val = min_val
            root.right = self.deleteNode(root.right, min_val)
            return root
        
        
def findMin(self, node):
    min_val = 0
    while node:
        min_val = node.val
        node = node.left
        
    return min_val

701 Insert Node in BST

• construct the node when root == null, otherwise just pass the node

public TreeNode insertNode(TreeNode root, TreeNode node) {
    if (root == null){
        return node;
    }    
    if (root.val > node.val){
        root.left = insertNode(root.left, node);
    }
    if (root.val < node.val){
        root.right = insertNode(root.right, node);
    }
    return root;
}

98 valid BST

• 不能直接跟root.left, root.right比

• 利用dfs設定邊界

public boolean isValidBST(TreeNode root) {
    return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

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

173 BST 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.

• Use a stack to store next smallest number

• apply addLeft method, add left nodes to stack

public class BSTIterator {
    private Stack<TreeNode> s = new Stack<>();

    public BSTIterator(TreeNode root) {
        addLeft(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !s.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode tmp = s.pop();
        addLeft(tmp.right);
        return tmp.val;
    }

    private void addLeft(TreeNode node){
        while(node != null){
            s.push(node);
            node = node.left;
        }
    }
}

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

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null){
        return null;
    }

    if (root.val <= p.val){
        return inorderSuccessor(root.right, p);
    }

    TreeNode left = inorderSuccessor(root.left, p);
    return left == null ? root : left;
}

510 Inorder Successor in BST II

Given a node in a binary search tree, find the in-order successor of that node in the BST. If that node has no in-order successor, return null. The Node has parent attribute

def inorderSuccessor(self, node: 'Node') -> 'Node':
    # if successor in right child
    if node.right:
        node = node.right
        while node.left:
            node = node.left
        return node

    # if successor in upper level (this including no successor case)
    while node.parent and node.parent.right == node:
        node = node.parent
    return node.parent

Search Range

• Recursion - create helper

public List<Integer> searchRange(TreeNode root, int k1, int k2) {
    List<Integer> result = new ArrayList<>();
    helper(root, k1, k2, result);
    return result;
}

private void helper(TreeNode root, int k1, int k2, List<Integer> result){
    if(root == null){
        return;
    }
    if(root.val > k1){
        helper(root.left, k1, k2, result);
    }

    if(root.val >= k1 && root.val <= k2){
        result.add(root.val);
    }

    if(root.val < k2){
        helper(root.right, k1, k2, result);
    }
}

firstGreaterThanK

• if node.data > k, record current node (no right tree on node.left)

public static BstNode<Integer> findFirstGreatThanK(BstNode<Integer> tree, Integer k){
    BstNode<Integer> subtree = tree, Result_node = null;
    while(tree != null){
        if (tree.data > k){
            Result_node = tree;
            tree = tree.left;
        }else{
            tree = tree.right;
        }
    }
    return Result_node;
}

230 find Kth smallest element in BST

• inorder

private int count;
private int ans;
public int kthSmallest(TreeNode root, int k) {
    count = 0;
    helper(root, k);
    return ans;
}

private void helper(TreeNode node, int k){
    if(node == null) return;
    if(count < k){
        helper(node.left, k);
        if(++count == k){
            ans = node.val;
            return;
        }
        helper(node.right, k);
    }
}

315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

"""
A tree node, with count value represent smaller counts
Traverse from end, build the tree and count number of smaller nodes
"""
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.count = 1 # 小於等於自己的node個數
        

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        if not nums: return []
        root = Node(nums[-1])
        res = [0]
        
        # starting from last 2nd idx in reverse order
        for n in nums[-2::-1]:
            count = self.insert(root, n)
            res.append(count)
        return res[::-1]
    
    def insert(self, node, val):
        count = 0
        while True:
            if val <= node.val:
                node.count += 1
                if not node.left:
                    node.left = Node(val)
                    break
                else:
                    node = node.left
            else:
                count += node.count
                if not node.right:
                    node.right = Node(val)
                    break
                else:
                    node = node.right
        return count