---
# System prepended metadata

title: LeetCode Data Structure

---

# LeetCode Data Structure
## Array
### 217. Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
* **Approach**
1. sort the array first, if the back number equals to front number, return true
2. or use the set in python
```python
class Solution(object):
    def containsDuplicate(self, nums):
        # nums=sorted(nums)
        # for i in range(1,len(nums)):
        #     if nums[i]==nums[i-1]:
        #         return True
        # return False

        #solution 2
        return len(nums)!=len(set(nums))
```
### 53. Maximum Subarray
Given an integer array nums, find the 
subarray which has the largest sum and return its sum.
```
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```
* **Approach**
1. linearly travel the list, and keep track of the current sum
2. if current sum<0 means that there is a negative number, and it is not helpful to us, so we reset the current sum. 
3. Note: In the loop, we need to check if currSum is less than 0 first, i.e., [-2,1], first round currSum will be -2, then in the second round, we check it first and find out that the currSum is less than 0, this means we don't need the previous value 
5. each round compare the current sum and the max sum to see if we need to update max sum
```python
class Solution(object):
    def maxSubArray(self, nums):
        maxSum = nums[0]
        currSum = 0
        for num in nums:
            # if currSum < 0 means that there is a negative number
            # so we reset the currSum since the negative number is not helpful to us
            if currSum < 0:
                currSum = 0
            currSum += num
            maxSum = max(maxSum, currSum)
        return maxSum
```
### 1. Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.
```
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
```
* **Approach**
use the map to store the difference between the nums[i] and the target
i.e. nums=[2,7,11,15]
nums[0]=2, not in map, so now map={7:0}, which means that the value of index 0 in nums need to plus 7 to get to the target
The next round nums[1]=7, which 7 is in the map, means the value of index 1 in nums can mathch with the value of index 0
```python
class Solution(object):
    def twoSum(self, nums, target):
        map={}
        for i in range(len(nums)):
            if nums[i] not in map:
                map[target-nums[i]]=i
            else:
                return map[nums[i]],i
```
### 88. Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
```
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
```
* Solution
```python
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        # compare the list reversely
        # 大的就先放到nums1的後面
        i, j = m-1, n-1
        for right in range(m+n-1, -1, -1):
            #nums2沒有資料，就直接輸出nums1即可
            if j < 0:
                break
            #nums1 index的值大於nums2的，所以擺到nums1後面相對的位子
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[right] = nums1[i]
                i -= 1
            else:
                nums1[right] = nums2[j]
                j -= 1
```
### 350. Intersection of Two Arrays II
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
```
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
```
* **Approach**
The map is used to store the appearing times of each value in the longer list, so if the value appear in the other list, corresponding map value will decrease 1
```python
class Solution(object):
    def intersect(self, nums1, nums2):
        result=[]
        # case1:nums2 is longer
        if len(nums1)<=len(nums2):
            map={}
            for i in range(len(nums2)):
                if nums2[i] not in map:
                    map[nums2[i]] = 1
                else:
                    map[nums2[i]] += 1
            for i in range(len(nums1)):
                if ((nums1[i] in map)and(map[nums1[i]]!=0)):
                    map[nums1[i]]-=1
                    result.append(nums1[i])
        
        # case2:nums1 is longer   
        else:
            map={}
            for i in range(len(nums1)):
                if nums1[i] not in map:
                    map[nums1[i]] = 1
                else:
                    map[nums1[i]] += 1
            for i in range(len(nums2)):
                if ((nums2[i] in map)and(map[nums2[i]]!=0)):
                    map[nums2[i]]-=1
                    result.append(nums2[i])
        return result
```
### 566. Reshape the Matrix
In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.

You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
* [tutorial](https://www.youtube.com/watch?v=JCb27sANkC0)
```python
class Solution(object):
    def matrixReshape(self, mat, r, c):
        """
        :type mat: List[List[int]]
        :type r: int
        :type c: int
        :rtype: List[List[int]]
        """
        row,col = len(mat),len(mat[0])
        if row*col != r*c:
            return mat
        else:
            #create a r*c matrix
            result = [[0 for _ in range(c)] for _ in range(r)]
            new_row = 0
            new_col = 0
            for i in range(row):
                for j in range(col):
                    #row-major
                    result[new_row][new_col] = mat[i][j]
                    
                    #if the column comes to the end, means we need to go to the next row and reset the column
                    new_col += 1
                    if new_col == c:
                        new_row += 1
                        new_col = 0
            return result
```
### 118. Pascal's Triangle
Given an integer numRows, return the first numRows of Pascal's triangle.
```
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
```
```python
class Solution(object):
    def generate(self, numRows):
        if numRows == 1:
            pascal = [[1]]
        elif numRows == 2:
            pascal = [[1],[1,1]]
        else:
            pascal = [[1],[1,1]]
            for i in range(2,numRows):
                layer=[]
                for idx in range(i+1):
                    if idx==0 or idx==i:
                        layer.append(1)
                    else:
                        layer.append(pascal[i-1][idx-1] + pascal[i-1][idx])
                pascal.append(layer)
        return pascal
```
### 36. Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

1. A Sudoku board (partially filled) could be valid but is not necessarily solvable.
2. Only the filled cells need to be validated according to the mentioned rules.

**Approach**

1. Use hashset to store the value in each row, col, and squares
2. defaultdict: https://ithelp.ithome.com.tw/articles/10193094
3. The way to check the 3*3 squares is to use // (integer division)
![](https://i.imgur.com/6wncCyY.jpg)

```python
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = collections.defaultdict(set)
        cols = collections.defaultdict(set)
        squares = collections.defaultdict(set)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if (board[r][c] in rows[r] or
                    board[r][c] in cols[c] or
                    board[r][c] in squares[(r//3, c//3)]):
                    return False
                rows[r].add(board[r][c])
                cols[c].add(board[r][c])
                squares[(r//3, c//3)].add(board[r][c])
        
        return True
```
### 74. Search a 2D Matrix
You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

**Approach**

1. Use two binary search
2. First search the correct row, we can compare the right most value or the left most value to move our pointers
3. After finding the correct row, use binary search to search the target in that row
```python
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        Rows, Cols = len(matrix), len(matrix[0])
        top, bottom = 0, Rows-1
        left, right = 0, Cols-1

        while top <= bottom:
            row = (top + bottom) // 2
            if target > matrix[row][-1]:
                top = row + 1
            elif target < matrix[row][0]:
                bottom = row - 1
            else:
                break
        
        if not (top <= bottom):
            return False
        row = (top + bottom) // 2

        while left <= right:
            col = (left + right) // 2
            if target == matrix[row][col]:
                return True
            elif target > matrix[row][col]:
                left = col + 1
            else:
                right = col - 1
        
        return False
```
## String
### 387. First Unique Character in a String
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
```
Input: s = "leetcode"
Output: 0
```
**Approach**

Use counter to count the appearing time of each character, then find the first character that just appear once
```python
class Solution:
    def firstUniqChar(self, s: str) -> int:
        num = Counter(s)
        for i in range(len(s)):
            if num[s[i]] == 1:
                return i
        
        return -1
```
### 383. Ransom Note
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.
```
Input: ransomNote = "aa", magazine = "aab"
Output: true
```
```python
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False
        
        ran, mag = Counter(ransomNote), Counter(magazine)
        
        for char in range(len(ransomNote)):
            if ransomNote[char] not in mag:
                return False
            elif ran[ransomNote[char]] > mag[ransomNote[char]]:
                return False
        
        return True
```
### 242. Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
```python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        sCount, tCount = Counter(s), Counter(t)
        return True if sCount == tCount else False
```
## Linked list
### 141. Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

![](https://i.imgur.com/7seRFPp.png)
```
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
```
```python
class Solution(object):
    def hasCycle(self, head):
        if not head:
            return False
        else:
            normal=head
            fast=head
            while fast and fast.next and fast.next.next:
                normal = normal.next
                fast = fast.next.next
                if normal == fast:
                    return True
            return False
```
### 21. Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.
```python
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        if ((not list1) and (not list2)): #both lists are empty
            return list1
        elif not list1 : #one of the list is empty
            return list2
        elif not list2:
            return list1
        else:
            result=current=ListNode() #current is the pointer for the result linked list
            while list1 and list2:
                if list1.val < list2.val:
                    current.next = list1 
                    current = list1 #update current pointer
                    list1 = list1.next #compare the next value
                else:
                    current.next = list2
                    current = list2
                    list2 = list2.next
            if list1:
                current.next = list1
            else:
                current.next = list2
            return result.next
```
### 203. Remove Linked List Elements
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

![](https://i.imgur.com/i02Rjek.png)
```
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
```
**Approach**

There are 3 situations, and we use two pointers prev and curr:
1. The current node.val is not equal to val, we can simply just move our prev and curr pointers, and the prev pointer is used to point the previous node of curr pointer
2. The current node is equal to val, but is at the first position, so we just move the head and curr pointer to the next node
3. The current node is equal to val and is not at the first position, so we let the prev.next = curr.next in order to jump through our val node
```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if not head:
            return head
        
        curr = head
        prev = None
        while curr:
            if curr.val != val:
                prev = curr
                curr = curr.next
            
            else:
                if curr == head:
                    head = head.next
                    curr = curr.next
                else:
                    prev.next = curr.next
                    curr = curr.next
        
        return head
```
### 206. Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
```python
class Solution(object):
    def reverseList(self, head):
        if not head:
            return head
        else:
            prev = None
            curr = None
            while head:
                curr = head
                head = head.next
                curr.next = prev
                prev = curr
            return curr 
```
### 83. Remove Duplicates from Sorted List
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

![](https://i.imgur.com/LZ4CT8L.png)
```
Input: head = [1,1,2,3,3]
Output: [1,2,3]
```
**Approach**

1. Use set to store the elements, and use two pointers prev and curr
2. If the val appears first time, add it to the set and move the pointers
3. If the val already appears, we can use prev.next = curr.next to jump through the node
```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        
        curr, prev = head, None
        num = set()
        
        while curr:
            if curr.val not in num:
                num.add(curr.val)
                prev = curr
                curr = curr.next
            else:
                prev.next = curr.next
                curr = curr.next
        
        return head
```
## Stack/Queue
### 20. Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Every close bracket has a corresponding open bracket of the same type.
```
Input: s = "()[]{}"
Output: true
```
**Approach**

Since the open brackets must be closed by the same type of brackets, so if we meet close bracket, we can check if the top of the stack is the corresponding open bracket
```python
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []

        for i in range(len(s)):
            if (s[i] == "(" or s[i] == "[" or s[i] == "{"):
                stack.append(s[i])
            else:
                if not stack:
                    return False               
                elif s[i] == ")":
                    tmp = stack.pop()
                    if tmp != "(": return False              
                elif s[i] == "]":
                    tmp = stack.pop()
                    if tmp != "[": return False
                elif s[i] == "}":
                    tmp = stack.pop()
                    if tmp != "{": return False
        
        return True if not stack else False
```
### 232. Implement Queue using Stacks
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.
Notes:

You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
```
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
```
```python
class MyQueue:

    def __init__(self):
        self.stack1, self.stack2 = [], []

    def push(self, x: int) -> None:
        self.stack1.append(x)

    def pop(self) -> int:
        if self.stack2:
            return self.stack2.pop()
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

    def peek(self) -> int:
        if not self.stack2:
            return self.stack1[0]
        else:
            return self.stack2[-1]

    def empty(self) -> bool:
        if self.stack1 or self.stack2:
            return False
        return True

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
```
## Tree
### 144. Binary Tree Preorder Traversal
```python
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        
        def preorder(root):
            if not root:
                return 
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)
        
        preorder(root)
        return res
```
### 94. Binary Tree Inorder Traversal
1. Recursion
```python
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        
        def inorder(root):
            if not root:
                return 
            inorder(root.left)
            res.append(root.val)   
            inorder(root.right)
        
        inorder(root)
        return res
```
2. Iterative
```python
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = []
        curr = root

        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            res.append(curr.val)
            curr = curr.right
        
        return res
```
### 145. Binary Tree Postorder Traversal
```python
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        
        def postorder(root):
            if not root:
                return             
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)
        
        postorder(root)
        return res
```
### 102. Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

![](https://i.imgur.com/BKDpJAQ.png)
```
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
```
```python
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        q = deque()
        curr = root

        if not root:
            return res
        
        q.append(curr)
        while q:
            num = len(q)
            level = []
            for i in range(num):
                curr = q.popleft()
                level.append(curr.val)
                if curr.left:
                    q.append(curr.left)
                if curr.right:
                    q.append(curr.right)
            
            res.append(level)
        return res
```
### 104. Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

![](https://i.imgur.com/fHWEQre.png)

```
Input: root = [3,9,20,null,null,15,7]
Output: 3
```
```python
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        L_height = self.maxDepth(root.left)
        R_height = self.maxDepth(root.right)
        
        return max(L_height, R_height) + 1
```
### 101. Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

![](https://i.imgur.com/AMX1D4u.png)
```
Input: root = [1,2,2,3,4,4,3]
Output: true
```
**Approach**
There are several situations
1. If the root is empty or the tree just has root node, then it is symmetric
2. Use two pointers to traverse both side, preoreder for left side and SRL for right side
3. If the node for both side is empty or have the same value, then is symmetric, otherwise is not

```python
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if ((not root) or (not root.left and not root.right)):
            return True
        
        def compare(lside, rside):
            if (not lside and not rside):
                return True
            if (not lside or not rside):
                return False
            
            if lside.val != rside.val:
                return False
            
            return (compare(lside.left, rside.right) and compare(lside.right, rside.left))
        
        return compare(root.left, root.right)
```
### 226. Invert Binary Tree
Given the root of a binary tree, invert the tree, and return its root.

![](https://i.imgur.com/1sTzzH0.png)

```
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
```
**Approach**

1. First invert the left subtree
2. Invert the right subtree
3. Invert the entire tree
```python
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        root.left, root.right = root.right, root.left
        return root
```
### 112. Path Sum
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

![](https://i.imgur.com/kaCbkvJ.png)

```
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
```
**Approach**

Use preorder traversal to scan the tree while compute the current sum
```python
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        
        def dfs(node, currSum):
            if not node:
                return False
            
            currSum += node.val
            if (not node.left and not node.right):
                return currSum == targetSum
            
            return (dfs(node.left, currSum) or dfs(node.right, currSum))
        
        return dfs(root, 0)
```
### 700. Search in a Binary Search Tree
You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

![](https://i.imgur.com/zDhHf6R.png)

```
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
```
```python
# 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 searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        curr = root
        while curr:
            if curr.val == val:
                return curr
            elif curr.val > val:
                curr = curr.left
            else:
                curr = curr.right
        
        return None
```
### 701. Insert into a Binary Search Tree
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

![](https://i.imgur.com/czkiSPC.png)

```
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
```
```python
# 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 insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        res = TreeNode()
        res.val = val
        if not root:
            return res
        
        curr, prev = root, None
        while curr:
            if curr.val > val:
                prev = curr
                curr = curr.left
            else:
                prev = curr
                curr = curr.right
        if prev.val > val:
            prev.left = res
        else:
            prev.right = res
        
        return root
```
### 98. Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid 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.

![](https://i.imgur.com/GQh7G4H.png)

```
Input: root = [5,1,4,null,null,3,6]
Output: false
```
**Approach**

![](https://i.imgur.com/cx66DeF.png)

```python
# 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: Optional[TreeNode]) -> bool:     
        
        def dfs(node, bottom, top):
            if not node:
                return True

            if not (bottom < node.val and node.val < top):
                return False

            return (dfs(node.left, bottom, node.val) and dfs(node.right, node.val, top))

        return dfs(root, -inf, inf)    
```
### 653. Two Sum IV - Input is a BST
Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

![](https://i.imgur.com/WmgCrHL.png)

```
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
```
```python
# 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 findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        order = []
        
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            order.append(node.val)
            inorder(node.right)
        inorder(root)

        need_val = {}
        for i in range(len(order)):
            if order[i] not in need_val:
                need_val[k - order[i]] = i
            else:
                return True

        return False    
```
### 235. Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

![](https://i.imgur.com/Jka5d1T.png)

```
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
```
```python
# 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':
        curr = root
        while curr:
            if curr.val == p.val or curr.val == q.val:
                return curr
            
            elif curr.val > p.val and curr.val > q.val:
                curr = curr.left
            
            elif curr.val < p.val and curr.val < q.val:
                curr = curr.right
            
            else:
                return curr
```