Tree Summary

Binary Tree, Binary Search Tree -> General Tree -> Graph

Tree concepts

• balanced tree: The constraint is generally applied recursively to every subtree. That is, the tree is only balanced if:
  • The left and right subtrees' heights differ by at most one, 2.
  • The left subtree is balanced, AND
  • The right subtree is balanced
• complete tree: a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
• full tree: A Binary Tree is full if every node has 0 or 2 children. In a Full Binary, number of leaf nodes is number of internal nodes plus 1.
• perfect tree: A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level. A Perfect Binary Tree of height h (where height is number of nodes on path from root to leaf) has 2h – 1 node.
• depth: The depth of a node is the number of edges from the node to the tree's root node. A root node will have a depth of 0.
• height: The height of a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0.
• binary search tree

Binary Tree and Binary Search Tree

• Trick: base case usually refers to the NULL ChildNode below the leaf node

public void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.println("x");
    preOrder(root.left);
    preOrder(root.right);
}

• Balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less.
• Complete binary tree: is a binary tree in which every level, except possibly the last, is completed filled, and all nodes are as far left as possible.
• Binary Search Tree: for every single node in the tree, the values in its left subtree are all smaller than its value, and the values in its right substree are all larger than its value.

questions:

• binary search tree rethink (search, insert, delete)
• Tree traversal rethink (in/pre/post-order): recursive, iterative iterator
• DFS rethink (recursion - not using side effect, backtracking - utilizing side effect , traversal)
• rethink divide conquer (root, root.left, root.right, 顺序 in／post/pre-order)