# Binary - Trees

## Inorder traversal
Left -> Node -> Right

# 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 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

## Preorder Traversal
Node -> Left -> Right

# 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 dfs(root): 
            if not root: 
                return  
            res.append(root.val) 
            dfs(root.left) 
            dfs(root.right) 
        dfs(root) 
        return res 

## Postorder traversal
Left -> Right -> Node

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = [] 
        def dfs(root): 
            if not root: 
                return 
            dfs(root.left) 
            dfs(root.right) 
            res.append(root.val) 
        dfs(root) 
        return res

# Binary Search Tree (BST)

## Binary Search Tree?

Hiểu đơn giản thì đây là Binary Tree nhưng có quy tắc đối với mỗi Node, các Node bên phải đều lớn hơn nó và các Node bên trái phải bé hơn nó.

## Problems

### Convert Sorted Array -> BST:
Sử dụng kĩ thuật `chia để trị - Divine and Conquer`: Node gốc là node giữa Array, đối với mỗi Node thì Node bên trái là Node ở Giữa - `mid` của Array con bên trái, tương tự với Node phải chỉ ngược chiều. Ta làm tuần tự theo công thức đệ quy cho đến khi không thể chia đôi mảng thành trái-phải được nữa:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: Optional[TreeNode]
        """
        def dnq(nums, l, r): 
            if l <= r: 
                mid = (l + r) // 2 
                node = TreeNode(nums[mid]) 
                node.left = dnq(nums, l, mid - 1) 
                node.right = dnq(nums, mid + 1, r)
            return node 
        return dnq(nums, 0, len(nums) - 1)

### Search in a BST
Để tìm 1 giá trị trong BST nhìn trung đơn giản hơn do ta không cần dùng đến đệ quy mà chỉ cần vòng lặp là đủ:

Đặc biệt với cấu trúc của BST, thay vì duyệt tất cả các Node ta có thể rút ngắn thời gian tìm kiếm còn $O(logn)$ bằng phương pháp tương tự như `binary search`:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: Optional[TreeNode]
        :type val: int
        :rtype: Optional[TreeNode]
        """
        while root: 
            if root.val == val: 
                return root 
            elif root.val > val: 
                root = root.left
            else: 
                root = root.right 
        return None

### Validate BST

Để kiểm tra 1 Binary Tree có phải là BST hay không, ta cần đảm bảo các điều kiện BST bằng cách:
- Với Mỗi Node: nhánh bên phải chỉ được chứa các Node có giá trị cao hơn nó
- Với Mỗi Node: nhánh bên trái chỉ được chứa các Node có giá trị nhỏ hơn nó.

=> Để làm được điều này, ta cần setup các giá trị `big` và `small`, dùng `dfs` duyệt tứng Node, và với mỗi Node:
- Nó phải đủ điều kiện là nằm trong khoảng `(small, big)`, nếu lọt thì đây không phải BST.
- Tiếp theo, với từng Node:
- Mỗi khi duyệt xuống nhánh trái: ta phải update `big` là giá trị của nó.
- Mỗi khi duyệt xuống nhánh phải: ta phải update `small` là giá trị của nó.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        check = [0] 
        def dfs(root, big, small): 
            if not root: 
                return 
            elif root.val >= big or root.val <= small: 
                check[0] += 1 
                return 
            
            dfs(root.left, root.val, small) #update big if go left
            dfs(root.right, big, root.val) # update small if go right
        dfs(root, float('inf'), float('-inf')) 
        return check[0] == 0

### Delete a Node in BST
Việc xóa Node mang giá trị `Key` trong BST khá tricky khi mà nó sẽ chia thành 2 trường hợp đối với cách giải đệ quy và 3 trường hợp khi dùng vòng lặp để xóa.

Để xóa ta tiến hành 2 bước chính:
- Tìm kiếm Node có giá trị `Key` để xóa.
- Xóa Node đó.

Để tìm 1 Node mang giá trị `Key` trong BST khá đơn giản và đã được trình bày từ trước.

Cái khó ở đây là khi đã tìm được Node mang `Key` rồi thì ta cần xử lý trường hợp:
1. Node là Node lá hoặc Node chỉ có 1 con (trường hợp này được tách ra trong cách giải vòng lặp).
- Ta sẽ tiến hành nối Node con của nó với cha. Hoặc nối Node cha với Null khi Node là Node lá.
2. Node là Node trong(tức là có 2 con).
- Khi này ta cần tìm `inorder successor - Node nhánh phải bé nhất` của Node hiện tại. Sau đó tiến hành thay giá trị của Node này bằng giá trị của `inorder successor`. Sau đó, xóa node `inorder successor`.

#### Sử dụng vòng lặp:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: Optional[TreeNode]
        :type key: int
        :rtype: Optional[TreeNode]
        """
        def find_successor(root): #Hàm tìm node nhỏ nhất bên trái của node hiện tại, đồng thời node cha của nó
            prev = None  
            while root: 
                if not root.left:  
                    break 
                prev = root 
                root = root.left 
            return prev, root 
        pre = None #Thiết lập con trỏ trước con trỏ sau
        cur = root 
        while cur: 
            if key > cur.val: #Tiến hành duyệt cây theo logic BST.
                pre = cur
                cur = cur.right 
            elif key < cur.val: 
                pre = cur 
                cur = cur.left 
            elif key == cur.val: #Nếu ta gặp node có chứa giá trị key, ta tiến hành xóa node đó theo 3 trường hợp đã được định nghĩa trên.
                if not cur.left and not cur.right: #Nếu là node lá
                    if pre == None: #Trường hợp chỉ có 1 node
                        root = None 
                        break 
                    elif pre.left == cur: #nếu đây là node lá trái của node cha
                        pre.left = None 
                        break
                    else: #nếu là node phải
                        pre.right = None
                        break 
                elif not cur.left or not cur.right: #Nếu node chỉ có 1 con 
                    if pre == None: #Trường hợp cần xóa là root. Ta xóa root và gán node mới là left hoặc right của nó tùy thuộc theo việc bên nào có tồn tại. 
                        if root.left: 
                            root = root.left
                            break
                        else: 
                            root = root.right 
                            break 
                    elif not cur.left: #Nếu chỉ có node con phải, ta sẽ tiến hành nối node cha của nó vào node phải của nó, tương tự với trường hợp chỉ có node trái ở dưới 
                        if pre.left == cur: 
                            pre.left = cur.right 
                            break
                        else: 
                            pre.right = cur.right 
                            break 
                    else: 
                        if pre.left == cur: 
                            pre.left = cur.left 
                            break
                        else: 
                            pre.right = cur.left
                            break 
                else: # Nếu gặp trường hợp cần xóa 1 node trong, ta sẽ cần phải thay đổi node đó thành node lớn nhất bên phải (inorder successor), đặc biệt nếu nó có node con ta cũng cần phải nối cả chúng vào nữa
                    prev, successor = find_successor(cur.right) 
                    cur.val = successor.val 
                    if prev != None:
                        prev.left = successor.right
                    else: 
                        cur.right = successor.right
                    break
        return root

#### Giải theo đệ quy:

# 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 deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root: #Basecase 1: Nếu node là Null, return 
            return root 
        # Tiến hành tìm kiếm Node có giá trị Key trong BST 
        # Đặc biệt, nếu ta có thể tìm được node chứa Key trong 1 trong các nhánh
        # trái hoặc phải của node hiện tại, ta sẽ tiến hành nối node hiện 
        # tại với nhánh đã bị biến đổi (cắt đi 1 node) 

        elif root.val < key: 
            root.right = self.deleteNode(root.right, key)
        elif root.val > key: 
            root.left = self.deleteNode(root.left, key)

        # Nếu tìm được node chứa Key: 
        # TH1: Node chỉ có 1 con hoặc là node lá, ta nối node cha của nó
        # vào node con của nó là xong
        elif root.val == key: 
            if not root.left: 
                return root.right 
            elif not root.right: 
                return root.left
            
            # TH2: Node là node trong (2 node): Ta cần thay giá trị của node 
            # bằng giá trị của node nhỏ nhất bên phải (inorder successor), 
            # sau đó, xóa node nhỏ nhất đó (điều này đơn giản vì nó sẽ là node rơi vào TH1)
            else:
                cur = root.right 
                while cur.left: 
                    cur = cur.left
                root.val = cur.val 
                root.right = self.deleteNode(root.right, cur.val) 
        return root