> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/binary_tree/bst.md).

# BST

## 99. Recover Binary Search Tree

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

Iterative

```python
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

```python
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

```python
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

```python
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

```java
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設定邊界

```java
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&#x20;

```java
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.

```java
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

```python
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

```java
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)

```java
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

```java
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]`.

```python
"""
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
                
        
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/binary_tree/bst.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.