Binary-tree model

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

                  Root [ 10 ]                <-- Level 0 (Depth 0, Height 2)
                 /           \
           [ 5 ]               [ 15 ]        <-- Level 1 (Depth 1, Height 1)
          /     \                   \
       [ 2 ]   [ 7 ]                 [ 20 ]  <-- Level 2 (Depth 2, Height 0)
        ^       ^                     ^
        |-------|---------------------|
             LEAF NODES (0 children)

Key Metrics & Formulas (for a tree with N nodes):
- Edges: Exactly N - 1 edges connect N nodes with zero cycles.
- Depth of Node: Number of edges from the root down to that node (Depth(Root) = 0).
- Height of Node: Number of edges on the longest downward path to a leaf (Height(Leaf) = 0).
- Tree Height: Height of the root node.
- Maximum Nodes at Level L: 2^L nodes.
- Maximum Nodes in Tree of Height H: 2^(H+1) - 1 nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

1. FULL BINARY TREE:
   Every node has strictly 0 or 2 children (no node has only 1 child).
          (1)
         /   \
       (2)   (3)
             /  \
           (4)  (5)

2. COMPLETE BINARY TREE (Crucial for Heaps!):
   All levels are completely filled except possibly the last, which is filled from LEFT to RIGHT.
          (1)
         /   \
       (2)   (3)
      /   \   /
    (4)  (5) (6)

3. PERFECT BINARY TREE:
   All internal nodes have 2 children, and all leaves are at the exact same depth.
   Total nodes = 2^(h+1) - 1.
          (1)
         /   \
       (2)   (3)
      / \   / \
    (4) (5) (6) (7)

4. BALANCED BINARY TREE:
   For every node, the height difference between left and right subtrees is at most 1.
   Guarantees tree height is O(log N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// Canonical Definition of a Binary Tree Node
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}