Binary Tree

Before we dive into this particular question, it's nice to go over the basic concept of binary tree:

1. The relationship is between "parent" node and "children" node. Except root, every child node has an unique parent, every parent can have left/right child.

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

2. size and height of a Tree:

size -

total # of the nodes that tree contains;

height -

the longest path from a root to its descendants.

//Recursively:
int size(Treenode *t){
  if (t == nullptr)
    return null;
  else
    return 1+size(t.left)+size(t.right)
}

//Iteratively:Using Stack to remember the root of both the left and right subtrees for each Treenode it visits in Stack
int size(Treenode *t){
  int sizeOfBT = 0;
  ArrayStack

The minimum height of a binary tree is :

log2(n+1)−1

3. BFS/DFS Traversal:

4. Perfect Binary Tree & Complete Binary Tree & Balanced Binary Tree:

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

Perfect Binary Tree is where:

1. All leaf nodes have the same depth;
2. All other(than leaf) nodes are full nodes

A recursive definition of a perfect binary tree is:

1. A single node with no children is a perfect binary tree of height h=0
2. A perfect Binary Tree with height h>0 is a node where both sub-trees are non-overlapping perfect binary trees of height h-1

Complete Binary Tree:

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Degenerate Tree:

A tree where every internal node has one child.

Well-balanced Tree:

Rather than letting them degrade to a worst-case behavior of O(n). To do that, we need to decide on a balance condition, which is to say that we need to understand what shape is considered well-enough balanced for our purposes, even if not perfect.

A "good" balance condition has two properties:

1. The height of a binary search tree meeting the condition is Θ(log n).
2. It takes O(log n) time to re-balance the tree on insertions and removals.