Binary Tree

Properties

1. The maximum number of nodes at level ‘l’ of a binary tree is 2^(l-1). [proof by induction]

2. Maximum number of nodes in a binary tree of height ‘h’ is 2^h– 1.

3. In a Binary Tree with N nodes, minimum possible height or minimum number of levels is ⌈ Log2(N+1) ⌉

4. A Binary Tree with L leaves has at least ⌈ Log2L ⌉ + 1 levels

Types of Binary Tree

1. Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children.

2. Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

3. Perfect Binary Tree: A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.

4. Balanced Binary Tree: A binary tree is balanced if height of the tree is O(Log n) where n is number of nodes.

Traversal Templates

Pre-order Traversal (non-recursive)

public class Template {
  public ArrayList<Integer> preorder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if(root == null) {
      return result;
    }
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while(!stack.isEmpty()) {
      TreeNode currt = stack.pop();
      result.add(currt.val);
      if(currt.right != null) {
        stack.push(currt.right);
      }
      if(currt.left != null) {
        stack.push(currt.left);
      }
    }
    return result;
  }
}

In-order Traversal (non-recursive)

public class Template {
  public ArrayList<Integer> inorder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if(root == null) {
      return result;
    }
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode currt = root;
    while(currt != null || !stack.isEmpty()) {
      while(currt != null) {
        stack.push(currt);
        currt = currt.left;
      }
      currt = stack.pop();
      result.add(currt.val);
      currt = currt.right;
    }
    return result;
  }
}

Level order Traversal

public class Template {
  public ArrayList<Integer> levelorder(TreeNode root) {
    ArrayList result = new ArrayList;
    if(root == null) {
      return result;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    while(!queue.isEmpty()) {
      ArrayList<Integer> level = new ArrayList<Integer>();
      //must take the size, bcause the size will change instantly
      int size = queue.size();
      for(int i = 0; i < size; i++) {
        TreeNode currt = queue.remove();
        level.add(currt.val)
        if(currt.left != null) {
          queue.add(currt.left);
        }
        if(currt.right != null) {
          queue.add(currt.right);
        }
      }
      result.add(level);
    }
    return result;
  }
}