Mastering Binary Trees, Searching, and Sorting Algorithms

Posted on Jun 9, 2026 in Computer Engineering

Understanding Trees and Hierarchical Data

Trees can feel like a big jump from linear data structures like arrays or linked lists, but they are incredibly intuitive once you see how they organize data hierarchically. Here is a clear, scannable breakdown of the core concepts, representations, traversals, and Binary Search Tree (BST) operations you need to know.

1. Definitions and Core Concepts

A Tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. It contains no cycles (you cannot loop back to a node without retracing your steps).

  • Root: The topmost node of the tree (the entry point).
  • Parent / Child: A node directly connected to another node moving down is the parent; the node below is the child.
  • Leaf Node: A node with no children (the endpoints of the tree).
  • Subtree: Any node and its descendants can be viewed as a smaller tree within the main tree.
  • Depth of a Node: The number of edges from the root to that specific node.
  • Height of a Tree: The length of the longest path from the root to a leaf node.
  • Binary Tree: A specific type of tree where each node can have at most 2 children (left and right child).

2. Representation of a Binary Tree

In memory, a binary tree is usually represented in one of two ways:

A. Sequential Representation (Arrays)

For a Complete Binary Tree, elements can be stored in a single 1D array. If a node is at index i (using 0-based indexing):

  • Left Child: Stored at index 2i + 1
  • Right Child: Stored at index 2i + 2
  • Parent: Found at index ⌊(i-1)/2⌋

Note: While great for space-saving in complete trees, this representation wastes memory if the tree has missing nodes (sparse trees).

B. Linked Representation (Pointers)

This is the most common approach. Each node is an object containing three components:

  1. Data: The actual value stored in the node.
  2. Left Pointer: A reference to the left child node.
  3. Right Pointer: A reference to the right child node.

Typical node structure in C/C++:

struct Node { int data; Node* left; Node* right; };

3. Binary Tree Traversals

Traversal means visiting every node exactly once. For binary trees, there are three classic depth-first strategies based on when you visit the Root relative to the Left (L) and Right (R) subtrees:

  • Preorder (Root → L → R): Visit the root first, then recursively traverse the left subtree, then the right subtree.
  • Inorder (L → Root → R): Traverse the left subtree first, visit the root, then traverse the right subtree. (Crucial fact: Inorder traversal of a BST always yields sorted data).
  • Postorder (L → R → Root): Traverse the left subtree, then the right subtree, and visit the root last.

Traversal Example

For a tree with 1 as root, 2 and 3 as children, and 4 and 5 as children of 2:

  • Preorder: 1 → 2 → 4 → 5 → 3
  • Inorder: 4 → 2 → 5 → 1 → 3
  • Postorder: 4 → 5 → 2 → 3 → 1

4. Binary Search Trees (BST)

A Binary Search Tree (BST) is a binary tree with a strict ordering rule: for any given node, all values in its left subtree must be less than the node’s value, and all values in its right subtree must be greater than the node’s value.

Core Operations

I. Searching

Because of the ordering rule, searching is efficient:

  1. Start at the root.
  2. If the target equals the current node, you found it.
  3. If the target is smaller, move to the left child.
  4. If the target is larger, move to the right child.

Time Complexity: O(h), where h is the height. In a balanced tree, this is O(log n).

II. Insertion

Trace down the tree comparing the new value to current nodes. Once you reach a NULL spot where the value should logically go, create a new node. Time Complexity: O(h).

III. Deletion

Deletion requires maintaining the BST structure:

  • Case 1 (Leaf): Simply remove the node.
  • Case 2 (One Child): Bypass the node by connecting the parent directly to the child.
  • Case 3 (Two Children): Replace the node with its Inorder Successor (smallest in right subtree) or Inorder Predecessor (largest in left subtree).

5. Searching Techniques

Searching finds the location of a target element within a collection.

A. Sequential Search (Linear Search)

Examine each element one by one. Works on any list. Time Complexity: O(n).

B. Binary Search

Divide and conquer. Look at the middle element; if the target is smaller, search the left half; if larger, search the right. Strict Condition: Data must be sorted. Time Complexity: O(log n).

6. Sorting Techniques

Sorting rearranges data into a specific order.

Simple Sorting Algorithms

  • Bubble Sort: Repeatedly swap adjacent elements if they are in the wrong order. Complexity: O(n²).
  • Selection Sort: Find the minimum element from the unsorted part and swap it with the first element. Complexity: O(n²).
  • Insertion Sort: Take one element at a time and insert it into its correct position within the sorted portion. Complexity: O(n²).

Advanced Sorting Algorithms

  • Merge Sort: Divide the array into sub-arrays, sort them, and merge them back together. Complexity: O(n log n).
  • Quick Sort: Pick a pivot, partition the array so smaller elements are on the left and larger on the right, then recurse. Complexity: O(n log n) average.