Binary Trees Explained: Structure, Traversals, Hashing and Sorting

Posted on Oct 15, 2026 in Computer Engineering

1. Explain Binary Tree

A Binary Tree is a non-linear, hierarchical data structure in which each node can have a maximum of two children, traditionally referred to as the left child and the right child.

Core Structural Components

• Root Node: The topmost node of the tree with no parent.
• Leaf Node: A node with no children (degree 0).
• Internal Node: A node containing at least one child.
• Subtree: A tree structure formed by a child node and its descendants.

Key Types of Binary Trees

• Full Binary Tree: Every node has either exactly 0 or 2 children.
• Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.
• Perfect Binary Tree: All internal nodes have exactly two children, and all leaves are at the exact same depth level.

2. Properties of Binary Tree

• Maximum Nodes at a Level: The maximum number of nodes at level \(l\) is \(2^{l}\) (assuming the root is at level 0).
• Maximum Total Nodes: The maximum number of nodes in a binary tree of height \(h\) is \(2^{h+1} – 1\).
• Minimum Total Nodes: The minimum number of nodes in a binary tree of height \(h\) is \(h + 1\) (which forms a skewed tree).
• Leaf vs. Internal Nodes: In any non-empty binary tree, if \(L\) is the number of leaf nodes and \(N_{2}\) is the number of nodes with exactly two children, then \(L = N_2 + 1\).
• Height Bounds: The minimum possible height of a binary tree with \(n\) nodes is \(\lfloor\log_2(n)\rfloor\).

3. Memory Representation of Binary Tree

A binary tree can be represented and stored in memory using two distinct approaches:

Sequential (Array) Representation

Nodes are stored linearly within a one-dimensional array. If a node is located at index \(i\) (using 0-based indexing):

• Left Child: Positioned at index \(2i + 1\).
• Right Child: Positioned at index \(2i + 2\).
• Parent Node: Located at index \(\lfloor(i-1)/2\rfloor\).

Drawback: Leads to severe memory waste for skewed or unbalanced trees, as empty positions must be filled with dummy values or NULL.

Linked List (Dynamic) Representation

Each node is created dynamically as a memory block or object consisting of three fields:

1. Left Pointer: Stores the memory address of the left child node.
2. Data: Stores the actual value or key of the node.
3. Right Pointer: Stores the memory address of the right child node.

4. Reconstruction of Binary Tree from Given Traversals

Given Elements:

• Inorder: 4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90
• Preorder: 25, 15, 10, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90

Step-by-Step Reconstruction Logic

1. Identify Root: The first element in a Preorder traversal is always the root. Root = 25.
2. Partition Inorder: Locate 25 in the Inorder list to split the elements into left and right subtrees:
   • Left Subtree (Inorder): 4, 10, 12, 15, 18, 22, 24
   • Right Subtree (Inorder): 31, 35, 44, 50, 66, 70, 90
3. Build Left Subtree: Look at the next element in Preorder (15). It becomes the root of the left subtree. Finding 15 in Inorder splits it into left (4, 10, 12) and right (18, 22, 24). Continuing this reveals 10 as a parent to 4 and 12, and 22 as a parent to 18 and 24.

1. Build Right Subtree: The first element in Preorder matching the right Inorder group is 50. Finding 50 in Inorder splits it into left (31, 35, 44) and right (66, 70, 90). Continuing this reveals 35 as a parent to 31 and 44, and 70 as a parent to 66 and 90.

Final Reconstructed Tree Layout

               25
             /    \
           15      50
          /  \    /  \
        10   22  35   70
       / \   / \ / \  / \
      4  12 18 24 31 44 66 90

5. Generate Inorder, Preorder, and Postorder

Assumption: Based on standard linear binary tree serialization formatting of the input sequential list, the structured parent-child node layout translates directly to:

         15
       /      \
     25        30
    /  \      /  \
   28   40  150   35
  / \   / \
 45 60 55 170

• Preorder (Root → Left → Right): 15, 25, 28, 45, 60, 40, 55, 170, 30, 150, 35
• Inorder (Left → Root → Right): 45, 28, 60, 25, 55, 40, 170, 15, 150, 30, 35
• Postorder (Left → Right → Root): 45, 60, 28, 55, 170, 40, 25, 150, 35, 30, 15

6. Hash Function and Collision Resolution

Hash Function

A Hash Function is a mathematical formula that maps an input key of arbitrary size to a fixed-size integer index value within the array bounds of a hash table.

Common Hashing Functions

• Division Method: \(h(\text{key}) = \text{key} \pmod m\), where \(m\) is the hash table size (ideally a prime number).

• Mid-Square Method: The key is squared (\(\text{key}^{2}\)), and a predefined number of digits are extracted from the middle of the result to serve as the index.
• Folding Method: The key is chopped into equal-sized parts, added together, and the lower digits form the final index.

Collision Resolution Techniques

A collision occurs when two distinct keys hash to the exact same index. They are resolved via two main strategies:

1. Open Addressing (Closed Hashing): All elements are kept inside the array table. If a slot is taken, other positions are checked:
   • Linear Probing: Searches the next positions sequentially (\(i+1, i+2, \dots\)).
   • Quadratic Probing: Searches positions at quadratic offsets from the original index.
   • Double Hashing: Employs a secondary hash function to calculate dynamic stride sizes.
2. Separate Chaining (Open Hashing): The hash table array holds head pointers to independent linked lists. Colliding items are added to the list at that slot.

7. Compare Between Linear Search and Binary Search

8. Apply Insertion, Selection, and Bubble Sort

Initial Array: [25, 15, 10, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90]

A. Bubble Sort (First 3 Passes)

Compares adjacent values and swaps them if they are out of order, moving the largest value to the end.

• Pass 1: [15, 10, 4, 12, 22, 18, 24, 25, 35, 31, 44, 50, 66, 70, 90] (90 floats to its end slot)
• Pass 2: [10, 4, 12, 22, 18, 24, 15, 25, 31, 35, 44, 50, 66, 70, 90] (70 floats to its end slot)
• Pass 3: [4, 10, 12, 18, 22, 15, 24, 25, 31, 35, 44, 50, 66, 70, 90]

B. Selection Sort (First 3 Passes)

Finds the absolute minimum item from the unsorted section and swaps it into the current target index.

• Pass 1: [4, 15, 10, 25, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90] (4 swapped with index 0 25)
• Pass 2: [4, 10, 15, 25, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90] (10 swapped with index 1 15)
• Pass 3: [4, 10, 12, 25, 15, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90] (12 swapped with index 2 15)

C. Insertion Sort (First 3 Shifts)

Inserts a key element into its relative correct index within a growing sorted left partition.

• Insertion 1 (Key=15): [15, 25, 10, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90]
• Insertion 2 (Key=10): [10, 15, 25, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90]
• Insertion 3 (Key=4): [4, 10, 15, 25, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90]