Trees

Tree:
Single root;
Each node (except the root) can have only one parent;
No cycle;

Tree一般指Binary Tree.

class TreeNode{
 int value;
 TreeNode left;
 TreeNode right;
}

Binary Search Tree: for all nodes left children <= current node <= right children
Balanced: the depth of the left and right subtrees of every node differ by 1 or less

In Java, built-in Balanced BST: TreeSet.

Applications:
Expression tree such as 48 * (3 + 8)
Decision tree.
File system
If root is most important: heap tree
Organized by character frequency: huffman tree
Organized by node ordering: Search tree

Basic Operations:
A. Depth-first search (go to the path until the end 一条道走到黑)
    比如走迷宫，最好用此策略。
    1. Binary Tree Preorder Traversal
    Visit your self, then visit all your left subtree, then all your right subtree.
    2. Binary Tree Inorder Traversal
    Visit all your left subtree, visit your self, then all your subtree.
    3. Binary Tree Postorder Traversal
    Visit all your left subtree, then all your right subtree, visit yourself.
B. Breath-first search
    比如social network, find your closet path to friend D.
    4. Binary Tree Level Order Traversal
    Use a queue (linkedlist) to keep the visited node, while the queue is not empty, every time a node is visited, remove it, and add its children to the list.

C. Binary Search Tree
    1. search / find Best O(1), Worst O(n), Average O(logn), so need balancing.
    Recursion / iteration

public boolean contains(E toFind) {
  TreeNode curr = root;
  int comp;
  while (curr != null) {
   comp = toFind.compareTo(curr.getData());
   if (comp < 0)
    curr = curr.getLeft();
   else if (comp > 0)
    curr = curr.getRight();
   else
    return true;
  }
  return false;
 }

    2. insert
    Recursion / iteration

public boolean insert(E toInsert) {
  TreeNode curr = root;
  int comp = toInsert.compareTo(curr.getData());
  while (comp < 0 && curr.getLeft() != null ||
    comp > 0 && curr.getRight() != null) {
   if (comp < 0) curr = curr.getLeft();
   else curr = curr.getRight();
   comp = toInsert.compareTo(curr.getData());
  }
  if (comp < 0)
   curr.addLeftChild(toInsert);
  else if (comp > 0)
   curr.addRightChild(toInsert);
  else return false;
  return true;
 }

    3. remove
    Remove leaf or a node with only one child is easy. If remove a node with two children, then find the smallest from the right subtree and replace the value with the value.

 Preorder transersal:
1. Recursive

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List preorderTraversal(TreeNode root) {
        List nodes = new ArrayList();
        if (root == null) {
            return nodes;
        }
        nodes.add(root.val);
        nodes.addAll(preorderTraversal(root.left));
        nodes.addAll(preorderTraversal(root.right));
        return nodes;
    }
}

2. Iteration (using a stack)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List preorderTraversal(TreeNode root) {
        List nodes = new ArrayList();
        if (root == null) return nodes;
        Stack nodetovisit = new Stack();
        nodetovisit.push(root);
        while(!nodetovisit.empty()) {
            TreeNode node = nodetovisit.pop();
            nodes.add(node.val);
            if (node.right != null) nodetovisit.push(node.right);
            if (node.left != null) nodetovisit.push(node.left);
        }
        return nodes;
    }
}

Inorder traversal:
1. Recursive

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList();
        if (root == null) return list;
        list.addAll(inorderTraversal(root.left));
        list.add(root.val);
        list.addAll(inorderTraversal(root.right));
        return list;
    }
}

2. Iteration

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList();
        Stack stack = new Stack();
        if (root == null) return list;
        TreeNode p = root;
        while (!stack.empty() || p != null) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode t = stack.pop();
                list.add(t.val);
                p = t.right;
            }
        }
        return list;
    }
}

Postorder traversal:
1. Recursive

public class Solution {
    public List postorderTraversal(TreeNode root) {
        // trivial recursion
        List list = new ArrayList();
        if (root == null) return list;
        list.addAll(postorderTraversal(root.left));
        list.addAll(postorderTraversal(root.right));
        list.add(root.val);
        return list;
    }
}

2. Iteration

Level Order Traversal:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List> levelOrder(TreeNode root) {
        // use two queue, current and next level
        List> lists = new ArrayList>();
        List list = new ArrayList();
        if (root == null) return lists;
        Queue current = new LinkedList();
        Queue next = new LinkedList();
        current.offer(root);
        while (!current.isEmpty()) {
            TreeNode node = current.poll();
            list.add(node.val);
            if (node.left != null) next.offer(node.left);
            if (node.right != null) next.offer(node.right);
            if (current.isEmpty()) {
                lists.add(list);
                Queue temp = current;
                current = next;
                next = temp;
                list = new ArrayList();
            }
        }
        return lists;
    }
}

Problems:
Leetcode 144 - Binary Tree Preorder Transversal
Leetcode 94 - Binary Tree Inorder Traversal