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

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