open-courses
Search…
Tree & Search

# Binary Tree

## Tree Representation

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

### Depth First Search (DFS)

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)

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]

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

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)$
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)$

### Insertion

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)$

### Deletion

1. 1.
如果是 leaf node：直接删除
2. 2.
如果只有一个 child：交换两个节点的值，并把 child node 删了
3. 3.
如果有两个 children：找到 inorder 遍历的下一个 node，交换两个节点的值，并把下一个 node 删除
# 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)$

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