# BST or Inorder

#### [701. Insert into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/)

```java
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}
```

#### [98. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)

{% tabs %}
{% tab title="Java" %}

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

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

{% endtab %}

{% tab title="Python" %}

```python
def isValidBST(self, root: TreeNode) -> bool:
    return self.helper(root, -sys.maxsize + 1, sys.maxsize)

def helper(self, curt, minv, maxv) :
    if not curt:
        return True
    if curt.val <= minv or curt.val >= maxv:
        return False
    return self.helper(curt.left, minv, curt.val) and self.helper(curt.right, curt.val, maxv)
```

{% endtab %}
{% endtabs %}

#### [450. Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/)

```java
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (key == root.val) {
        if (root.left == null && root.right == null) {
            return null;
        } else if (root.right == null) {
            return root.left;
        } else {
            TreeNode swap = findSwap(root.right);
            root.val = swap.val;
            root.right = deleteNode(root.right, swap.val);
        }
    } else if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

private TreeNode findSwap(TreeNode curt) {
    while (curt.left != null) {
        curt = curt.left;
    }
    return curt;
}
```

#### [235. Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)

```java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } 
    return root;
}
```

#### [865. Smallest Subtree with all the Deepest Nodes](https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/)

An upgrade version of 235. Need to output LCA as well as count depth.

```java
public TreeNode subtreeWithAllDeepest(TreeNode root) {
    return helper(root).node;
}

private Result helper(TreeNode root) {
    if (root == null) {
        return new Result(0, null);
    }
    Result L = helper(root.left);
    Result R = helper(root.right);
    if (L.depth > R.depth) {
        return new Result(L.depth + 1, L.node);
    } else if (L.depth < R.depth) {
        return new Result(R.depth + 1, R.node);
    }
    return new Result(L.depth + 1, root);
}

class Result {
    int depth;
    TreeNode node;
    public Result(int depth, TreeNode node) {
        this.depth = depth;
        this.node = node;
    }
}
```

#### [538. Convert BST to Greater Tree](https://leetcode.com/problems/convert-bst-to-greater-tree/)

Reverse in-order traversal, add the increment to the node and update the increment.&#x20;

```java
int val = 0;
public TreeNode convertBST(TreeNode root) {
    helper(root);
    return root;
}

private void helper(TreeNode curt) {
    if (curt == null) return;
    helper(curt.right);
    curt.val += val;
    val = curt.val;
    helper(curt.left);
}
```

#### [270. Closest Binary Search Tree Value](https://leetcode.com/problems/closest-binary-search-tree-value/)

{% tabs %}
{% tab title="Java" %}

```java
public int closestValue(TreeNode root, double target) {
    return helper(root, root.val, target);
}

private int helper(TreeNode root, int min, double target) {
    if (root == null) return min;
    
    if (Math.abs(root.val - target) < Math.abs(min - target)) {
        min = root.val;
    }
    if (root.val > target) {
        min = helper(root.left, min, target);
    } else {
        min = helper(root.right, min, target);
    }
    return min;
}
```

{% endtab %}

{% tab title="Python" %}

```python
    def closestValue(self, root: TreeNode, target: float) -> int:
        self.res = root.val
        self.helper(root, target)
        return self.res
    
    def helper(self, curt, target) :
        if not curt:
            return
        if abs(curt.val - target) < abs(self.res - target):
            self.res = curt.val
        if target < curt.val:
            self.helper(curt.left, target)
        else:
            self.helper(curt.right, target)
```

{% endtab %}
{% endtabs %}

#### [272. Closest Binary Search Tree Value II](https://leetcode.com/problems/closest-binary-search-tree-value-ii/)

Inorder traversal the tree and maintain a list. Treat the list as a deque or linkedlist. Add nodes to the back, pop first if the first nodes is farther than curt val. Therefore all nodes in the list are the closest to target when the list size is larger than k. **When the first node is closer target than current node. It means all results are found, return.**

This is similar as sliding window on an array and maintain the closest values.

```java
public List<Integer> closestKValues(TreeNode root, double target, int k) {
    LinkedList<Integer> list = new LinkedList<>();
    helper(root, target, k, list);
    return list;
}

private void helper(TreeNode root, double target, int k, LinkedList<Integer> list) {
    if (root == null) return;
    helper(root.left, target, k, list);
    if (list.size() >= k) {
        if (!list.isEmpty() && Math.abs(list.peekFirst() - target) > Math.abs(root.val - target)) {
            list.pollFirst();
        } else {
            return;
        }
    }
    list.add(root.val);
    helper(root.right, target, k, list);
}
```

#### [938. Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/)

3 scenarios:

* L R < root.val
* root.val < L R
* L < root.val < R

```python
sum = 0;
def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
    self.helper(root, L, R)
    return self.sum
    
def helper(self, root, L, R):
    if not root:
        return
    if root.val < L and root.val < R:
        self.helper(root.right, L, R)
    elif root.val > L and root.val > R:
        self.helper(root.left, L, R)
    else:
        self.sum += root.val
        self.helper(root.left, L, R)
        self.helper(root.right, L, R)
```

#### [173. Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/)

Solution1. Inorder traversal and store all results in a list

Solution2: Iteration Inorder traversal by using Stack

```java
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushAll(root);
    }

    private void pushAll(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    /** @return the next smallest number */
    public int next() {
        if (!hasNext()) return -1;
        TreeNode curt = stack.pop();
        pushAll(curt.right);
        return curt.val;
    }

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

Solution3: Morris traversal:

```java
TreeNode curt;
public BSTIterator(TreeNode root) {
    this.curt = root;
}

/** @return the next smallest number */
public int next() {
    Integer res = null;
    while (curt != null) {
        if (curt.left == null) {
            res = curt.val;
            curt = curt.right;
            break;
        } else {
            TreeNode pre = curt.left;
            while (pre.right != null && pre.right != curt) {
                pre = pre.right;
            }
            if (pre.right == null) {
                pre.right = curt;
                curt = curt.left;
            } else {
                pre.right = null;
                res = curt.val;
                curt = curt.right;
                break;
            }
        }
    }
    return res;
}

/** @return whether we have a next smallest number */
public boolean hasNext() {
    return curt != null;
}
```

#### [285. Inorder Successor in BST](https://leetcode.com/problems/inorder-successor-in-bst/)

```java
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode succ = null;
    Stack<TreeNode> stack = new Stack<>();
    addLeft(root, stack);
    while (!stack.isEmpty()) {
        TreeNode pop = stack.pop();
        addLeft(pop.right, stack);
        if (pop == p && !stack.isEmpty()) {
            succ = stack.peek();   
            break;
        }
    }
    return succ;
}

private void addLeft(TreeNode curt, Stack<TreeNode> stack) {
    while (curt != null) {
        stack.add(curt);
        curt = curt.left;
    }
}
```

#### [99. Recover Binary Search Tree](https://leetcode.com/problems/recover-binary-search-tree/)

Inorder traverse this tree, use pre to record the previous node, at each node check `if pre != null && A == null && pre.val >= curt.val`. If so, set the A to pre, which means A is a candidate. `if pre != null && A != null && pre.val >= curt.val` then B is another candidate. For example,

&#x20;       A B&#x20;

&#x20;1 2 4 3 5

Then swap the value of A and B.

```java
TreeNode A;
TreeNode B;
TreeNode pre;
public void recoverTree(TreeNode root) {
    helper(root);
    int temp = A.val;
    A.val = B.val;
    B.val = temp;
}

private void helper(TreeNode curt) {
    if (curt == null) return;
    helper(curt.left);
    if (pre != null && A == null && pre.val >= curt.val) {
        A = pre;     
    }
    if (pre != null && A != null && pre.val >= curt.val) {
        B = curt;
    }
    pre = curt;
    helper(curt.right);
}
```

#### [1214. Two Sum BSTs](https://leetcode.com/problems/two-sum-bsts/)

Two Sum approach:  *O(n^2)*

```java
public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
    if (root1 == null || root2 == null) return false;
    if (root1.val + root2.val == target) return true;
    else if (root1.val + root2.val > target) {
        return twoSumBSTs(root1.left, root2, target)
             || twoSumBSTs(root1, root2.left, target);
    } else {
        return twoSumBSTs(root1.right, root2, target)
             || twoSumBSTs(root1, root2.right, target);
    }
}
```

Set approach: *T: O(n)  S: O(n)* &#x20;

```java
public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
    Set<Integer> set = new HashSet<>();
    traverse(root1, set);
    return traverse2(root2, set, target);
}

private void traverse(TreeNode root, Set<Integer> set) {
    if (root == null) return;
    set.add(root.val);
    traverse(root.left, set);
    traverse(root.right, set);
}

private boolean traverse2(TreeNode root, Set<Integer> set, int target) {
    if (root == null) return false;
    if (set.contains(target - root.val)) return true;
    return traverse2(root.left, set, target) || traverse2(root.right, set, target);
}
```

#### [333. Largest BST Subtree](https://leetcode.com/problems/largest-bst-subtree/)

```java
int max = 1;
public int largestBSTSubtree(TreeNode root) {
    if (root == null) {
        return 0;
    }
    helper(root);
    return max;
}

private Result helper(TreeNode root) {
    if (root == null) {
        return new Result(true, 0);
    }
    Result L = helper(root.left);
    Result R = helper(root.right);
    Result res = new Result(false, 0);
    int Lbound = L.max == null ? Integer.MIN_VALUE : L.max;
    int Rbound = R.min == null ? Integer.MAX_VALUE : R.min;
    if (L.isBST && R.isBST && root.val > Lbound && root.val < Rbound) {
        res.size = L.size + R.size + 1;
        res.min = L.min == null ? root.val : L.min;
        res.max = R.max == null ? root.val : R.max;
        res.isBST = true;
        max = Math.max(max, res.size);
        return res;
    } 
    return res;
}

class Result {
    Integer min, max;
    boolean isBST;
    int size;
    Result(boolean isBST, int size) {
        this.isBST = isBST;
        this.size = size;
    }
}
```


---

# Agent Instructions: 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://howardyangemail.gitbook.io/decode-leetcode/tree/inorder.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.