Tree

• 各种二叉树的定义

  • 每个节点children = 0 / 2, 为 full binary tree
  • 按level order 从左到右依次(尽量)填满，为complete binary tree

• BT

  • ->traversal algo(preorder, inorder, postorder, level order, vertical order, morris(recover BST)

• Complete BT

  • -> tree representation using array

  • -> sometimes, use hash map to represent a tree, key: location, val: TreeNode)

• BST

  • -> inorder traversal

    • -> sorted array in ascending order

    • -> range for each node in BST, [左子树max, 右子树min)

  • -> practical problems => modified BST (building BST is very important, need to know the # of nodes in left subtree)

• Fenwick Tree

  • motivation: given a 1D array of n elements, naive implementation for query and update, or we can use DP to pre-compute the prefix sums in O(n), but what if the values of elements can change? Fenwick tree was proposed to solve the prefix sum problem. The idea is to store partial sum in each node and get total sum by traversing the tree from leaf to root. The tree has a height of log(n)

  • runtime complexity: build: O(n log n), update: O(log n), query: O(log n)

  • space complexity: O(n)

• recursive DFS()

  • -> from top to bottom -> preorder, inorder (very important) <=> iterative solution

  • -> from bottom to top -> postorder (very important)

• iterative DFS()

  • stack + Tuple(private class Tuple)