# Tree & Search

本节内容为自己整理，是 Graph & Search 的子集。示例中皆假设不同节点的值不同。

## Binary Tree

### Tree Representation

```python
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
```

### Tree Search

#### Depth First Search (DFS)

方法 1：使用递归

```python
def dfs(root):
    if not root:
        return
    # preorder: action on root.val
    left_val = dfs(root.left)
    # inorder: action on root.val
    right_val = dfs(root.right
    # postorder: action on root.val
    return func(left_val, right_val)
```

方法 2：使用栈迭代

```python
def dfs_preorder(node):
    if not node:
        return
    stack = [node]
    while stack:
        node = stack.pop()
        # from right to left
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

def dfs_postorder(node):
    if not node:
        return
    stack = [node]
    
    ret = []
    while stack:
        node = stack.pop()
        ret.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return ret[::-1]
```

#### Breadth First Search (BFS)

方法1：使用 list

```python
def bfs(root):
    if not root:
        return
    q = [root]
    while q:
        nq = []
        for node in q:
            if node.left:
                nq.append(node.left)
            if node.right:
                nq.append(node.right)
        q = nq
```

方法2：使用 dequeue

```python
from collections import dequeue
def bfs(root):
    if not root:
        return
    q = dequeue([root])
    while q:
        node = q.popleft()
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
```

### Binary Search Tree (BST)

BST 是一种特殊的 Binary Tree，其中任意节点都满足：

* 左子树中所有节点的值都小于当前节点的值
* 右子树中所有节点的值都大于当前节点的值

BST 的一些特性罗列如下：

* 通过 in-order traversal 可以得到所有节点按 key 排序的结果
* 擅长做一些特殊查询
  * 查询与某 key 大小最相近的元素（closest lower/greater elements）
  * 区间查询（range queries）
* 如果是 Self-Balancing BST（Red-Black Tree, AVL Tree, Splay Tree）则所有操作的复杂度为 $$\theta(logn)$$ 

#### Search

```python
def search(root, key):
    if root is None or root.val == key:
        return root
    if root.val < key:
        return search(root.right, key)
    return search(root.left, key)
```

Time complexity: $$O(h)$$&#x20;

#### Insertion

```python
def insert(root, node):
    if root is None:
        root = node
    else:
        if roo.val < node.val:
            if root.right is None:
                root.right = node
            else:
                insert(root.right, node)
        else:
            if root.left is None:
                root.left = node
            else:
                insert(root.left, node)
```

Time complexity: $$O(h)$$&#x20;

#### Deletion

删除的时候分三种情况考虑：

1. 如果是 leaf node：直接删除
2. 如果只有一个 child：交换两个节点的值，并把 child node 删了
3. 如果有两个 children：找到 inorder 遍历的下一个 node，交换两个节点的值，并把下一个 node 删除

```python
# Given a non-empty binary search tree, return the node
# with minimum key value found in that tree.
def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def deleteNode(root, key):
    if root is None:
        return root
    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif key > root.key:
        root.right = deleteNode(root.right, key)
    else:
        if root.left is None:
            root = root.right
            return root
        elif root.right is None:
            root = root.left
            return root
        next_node = minValueNode(root.right)
        root.key = next_node.key
        root.right = deleteNode(root.right, next_node.key)
    return root  
```

Time complexity: $$O(h)$$&#x20;

#### Traversal

* In-order traversal of BST always produces sorted output
* we can construct a BST with only Preorder or Postorder or Level Order traversal.
* number of unique BSTs with n distinct keys is Catalan Number

#### 算法题集锦：

* Search
  * [Search in a Binary Search Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/)
* Pre-order Traversal
  * [Print Binary Tree](https://leetcode.com/problems/print-binary-tree/)
  * [Maximum Binary Tree](https://leetcode.com/problems/maximum-binary-tree/)
  * [Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)
  * [Binary Tree Paths](https://leetcode.com/problems/binary-tree-paths/)
  * [Second Minimum Node In a Binary Tree](https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/)
  * [Find Mode in Binary Search Tree](https://leetcode.com/problems/find-mode-in-binary-search-tree/)
  * [Verify Preorder Serialization of a Binary Tree](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/)
  * [Merge Two Binary Trees](https://leetcode.com/problems/merge-two-binary-trees/)
  * [Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)
* In-order Traversal
  * [Flatten Binary Tree to Linked List](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/)
  * [Binary Tree In-order Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)
  * [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)
  * [Increasing Order SearchTree](https://leetcode.com/problems/increasing-order-search-tree)
* Post-order Traversal:
  * [Binary Tree Tilt](https://leetcode.com/problems/binary-tree-tilt/)
  * [Univalued Binary Tree](https://leetcode.com/problems/univalued-binary-tree/)
  * [Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/)
  * [Binary Tree Cameras](https://leetcode.com/problems/binary-tree-cameras/)
  * [Binary Tree Pruning](https://leetcode.com/problems/binary-tree-pruning/)
  * [Unique Binary Search Trees II](https://leetcode.com/problems/unique-binary-search-trees-ii/)
  * [Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)
* Breadth First/Level Order Search
  * [Maximum Width of Binary Tree](https://leetcode.com/problems/maximum-width-of-binary-tree/)
  * [Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)
  * [Binary Tree Level Order Traversal II](https://leetcode.com/problems/binary-tree-level-order-traversal-ii/)
* Construction
  * [Convert Sorted List to Binary Search Tree](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/)
  * [Construct Binary Tree from In-order and Post-order Traversal](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
* Complete Tree
  * [Count Complete Tree Node](https://leetcode.com/problems/count-complete-tree-nodes/)
* Dynamic Programming
  * [Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/)
* Graph Search
  * [All Nodes Distance K in Binary Tree](https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/)


---

# 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://zhenghe.gitbook.io/open-courses/mit-6.006/tree-and-search.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.