Binary Tree Representation

# CHAPTER 4

Binary Tree Representation #

1. Introduction #

2. Learning Objectives #

• Construct a Binary Tree using Linked Node representation.

• Construct a Complete Binary Tree using Array representation.

• Apply mathematical index formulas to find Left/Right children in an Array.

• Evaluate the critical memory tradeoffs between Pointers and Arrays.

3. Linked Representation (Using Pointers) #

The Node Structure:

1. 1. A data variable (Integer, String, etc.)

1. 2. A Pointer variable pointing to the Left Child's RAM address.

1. 3. A Pointer variable pointing to the Right Child's RAM address.

*(If a child does not exist, the pointer is explicitly set to NULL / None).*

Visualizing Memory:

[Data: 10 | Left: 0x2A | Right: 0x5F]  --> Root

Pros: Extremely dynamic. You can insert or delete nodes infinitely without resizing memory blocks. Excellent for chaotic, unbalanced trees. Cons: Pointers consume extra physical RAM.

4. Array Representation (Using Index Math) #

The Array Layout (1-Indexed Array): Insert the Root at Index 1. Read the tree level-by-level, left-to-right, sliding the data into subsequent array slots.

The Index Math Formulas: If a Node is located at Array Index $i$:

• Its Left Child is located at Index $2 \times i$

• Its Right Child is located at Index $(2 \times i) + 1$

• Its Parent is located at Index $\lfloor i / 2 \rfloor$

Example Tree:

        A(1)
       /    \
     B(2)   C(3)
    /  \
  D(4) E(5)

Array: [null, A, B, C, D, E] *Math Check:* Where is B's left child? $B$ is at Index 2. Left child = $2 \times 2 = 4$. Index 4 holds $D$. The math flawlessly simulates physical edges in $O(1)$ time!

Pros: Blisteringly fast $O(1)$ access. Zero RAM wasted on pointers. Highly cache-friendly. Cons: Catastrophic for Degenerate (unbalanced) trees. If you have a straight-line right-leaning tree of 10 nodes, the mathematical array index requires $2^{10}$ ($1024$) slots of memory, wasting 1014 slots of empty null space!

5. Code Example: Array Simulation #

Python:

tree_array = [None, 'A', 'B', 'C', 'D', 'E'] # 1-Indexed

def get_left_child(index):
    return tree_array[2 * index]

def get_parent(index):
    import math
    return tree_array[math.floor(index / 2)]

# Find B's Parent (B is at index 2)
parent = get_parent(2)
print(f"Parent of B is: {parent}") # Output: A

# Find B's Left Child
left_child = get_left_child(2)
print(f"Left child of B is: {left_child}") # Output: D

6. Complexity Analysis #

• Space Complexity: $O(N)$ (Data + 2 Pointers per node).

• Expansion Time: $O(1)$ instant dynamic memory allocation.

Array Representation:

• Space Complexity (Complete Tree): $O(N)$ (Perfect packing).

• Space Complexity (Degenerate Tree): $O(2^N)$ (Catastrophic memory waste).

7. Common Mistakes #

• Using Arrays for heavily modified trees: If your tree constantly deletes nodes and re-balances, do not use an Array. Shifting hundreds of elements across a linear array to fix the gaps takes $O(N)$ time and destroys CPU efficiency. Use linked pointers!

8. Best Practices #

• Use Linked Representation for standard Binary Search Trees (BST) and dynamic applications.

• Use Array Representation exclusively for strict Binary Heaps (Priority Queues), where the Complete Tree structure is mathematically guaranteed.

9. Exercises #

1. 1. Given an Array Representation [null, 10, 20, 30, 40, 50, 60, 70], calculate the mathematical index of node 30's Right Child, and identify its value.

1. 2. Write a function in Java or C++ that returns the Right Child of a linked node structure.

10. MCQs with Answers #

11. Interview Questions #

• Q: How do the Left/Right child mathematical formulas change if you use a 0-Indexed Array instead of a 1-Indexed array? *(Answer: Left child becomes (2*i) + 1. Right child becomes (2*i) + 2. Parent becomes (i-1) / 2).*

• Q: Discuss the memory tradeoffs between Pointers and Arrays for a massive 1 Billion node system.

12. Summary #

13. Next Chapter Recommendation #