Binary Trees Basics

# CHAPTER 3

Binary Trees Basics #

1. Introduction #

2. Learning Objectives #

• Define the mathematical constraints of a Binary Tree.

• Identify Left and Right Children.

• Distinguish between Full, Complete, Perfect, and Degenerate Binary Trees.

• Understand the mathematical properties of a Binary Tree's geometry.

3. What is a Binary Tree? #

1. 1. The Left Child

1. 2. The Right Child

A node in a Binary Tree can have:

• Exactly 0 children (A Leaf node)

• Exactly 1 child (Left OR Right)

• Exactly 2 children (Left AND Right)

Visual Example:

        A
       / \
      B   C
     /     \
    D       E

4. Types of Binary Trees #

1. Full Binary Tree (Strict Binary Tree): Every node has either exactly 0 children or exactly 2 children. There are absolutely no nodes with just 1 child.

        A
       / \
      B   C
         / \
        D   E

2. Complete Binary Tree: Every single level of the tree is completely filled with nodes, except possibly the very last level. Furthermore, the last level must be filled from Left to Right without any gaps. (This shape is mandatory for creating Heaps).

        A
       / \
      B   C
     / \  /
    D   E F

3. Perfect Binary Tree: The most geometrically beautiful tree. It is both Full and Complete. Every internal node has exactly 2 children, and every single leaf node is on the exact same bottom level.

        A
       / \
      B   C
     / \ / \
    D  E F  G

4. Degenerate (Pathological) Binary Tree: Every internal node has exactly 1 child. The tree acts exactly like a sluggish Linked List, plunging in a single straight line.

    A
     \
      B
       \
        C

5. Mathematical Properties of Binary Trees #

• Maximum nodes at Level L: $2^L$ (Level 0 has 1, Level 1 has 2, Level 2 has 4).

• Maximum nodes in a Perfect Tree of Height H: $2^{H+1} - 1$.

• Example: A perfect tree of height 2 has $2^{3} - 1 = 8 - 1 = 7$ nodes.

• Minimum Height of a tree with N nodes: $\log_2(N+1) - 1$. (This logarithmic height is what makes searching so incredibly fast!).

6. Code Representation Structure #

C / C++:

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    
    // Constructor
    Node(int val) {
        data = val;
        left = NULL;
        right = NULL;
    }
};

Java:

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

Python:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

7. Common Mistakes #

• Confusing Full vs. Complete Trees: A Full tree can be lopsided (as long as nodes have 0 or 2 children). A Complete tree cannot be lopsided; it must be tightly packed level-by-level, left-to-right.

• Forgetting Degenerate Trees: When evaluating an algorithm, do not assume your Binary Tree looks like a perfect pyramid. Always consider the worst-case scenario: a Degenerate Tree that acts like a $O(N)$ Linked List!

8. Best Practices #

• Always check if the left and right pointers are NULL (or None) before attempting to access their data to avoid Null Pointer Exception crashes.

9. Exercises #

1. 1. Draw a Complete Binary Tree with 6 nodes.

1. 2. Calculate the maximum number of nodes possible in a Perfect Binary Tree with a height of 3.

10. MCQs with Answers #

Q8. True or False: Every Complete Binary Tree is also a Perfect Binary Tree. a) True b) False Answer: b) False. A complete tree might have an incomplete bottom row, disqualifying it from being perfect.

11. Interview Questions #

• Q: How do you mathematically differentiate the worst-case Time Complexity between a Perfect Binary Tree and a Degenerate Binary Tree?

• Q: Is a single node with no children considered a Full Binary Tree? *(Answer: Yes. It has exactly 0 children, satisfying the 0 or 2 rule).*

12. Summary #

13. Next Chapter Recommendation #