This week’s issue brings you:

• A User-Friendly Guide to Binary Trees

• Reverse Proxy vs Load Balancer — What’s The Difference (Recap)

• Data Structures in The Real World (Recap)

• Database Indexing Explained (Recap)

READ TIME: 5 MINUTES

A User-Friendly Guide to Binary Trees

Searching, sorting, pathfinding, machine learning, database indexing, the list can go on and on.

Binary trees play a critical role in programming.

This data structure not only simplifies data storage and access but also enhances efficiency in myriad operations pivotal to software development.

Today we’ll explore this fundamental data structure. Let’s jump in!

Understanding Binary Trees

A binary tree is a tree data structure where each node has no more than two children.

It’s a structured collection of nodes, each holding data and references to up to two children, termed as the left and right child.

The beauty of a binary tree lies in its simplicity and utility in representing hierarchical data.

The root node sits at the apex, serving as the entry point to the tree, while leaves (nodes without children) mark the boundaries of this structure.

A binary tree can come in many forms, such as the following:

Full binary tree

Every node has either zero or two children.

Complete binary tree

Each level of the tree has a complete set of nodes, with the last level being the exception.

Perfect binary tree

Every level of the tree including the last level is complete.

Balanced binary tree

The depth of the left and right sub-trees of all nodes differ by no more than 1.

Binary search tree

Each node is larger than all the nodes in their left sub-tree, and smaller than all the nodes in their right sub-tree.

Implementing Binary Trees

Classes are often used to implement binary trees because of their ability to use encapsulation and abstraction.

A Node class encapsulates the value and references to child nodes, laying the foundation for more complex operations.

An insert function would be used to add a value relative to a given root node.

Based on your use case, you may want to have other methods like search and traverse.

Applications of Binary Trees

Binary trees find their utility in a vast array of applications, from enhancing search algorithms and sorting mechanisms to managing hierarchical data such as filesystems.

In search algorithms, BSTs (binary search trees) dramatically reduce the time complexity, often to O(log n) for balanced trees.

Sorting algorithms, like tree sort, leverage in-order traversal to achieve efficient sorting.

Pathfinding algorithms in gaming and real-world mapping applications utilize binary trees for efficient route calculation.

Advanced Topics in Binary Trees

Moving beyond fundamental binary trees, we encounter advanced structures like AVL trees and Red-Black trees. These self-balancing binary search trees incorporate mechanisms to maintain balance, ensuring operational efficiency is preserved.

Common challenges include tree traversal without recursion, identifying the lowest common ancestor in a tree, and methods to balance an unbalanced tree, each presenting unique problem-solving opportunities.

AVL Trees are preferred in scenarios where lookups are more frequent than insertions/deletions, due to their stricter balancing, which ensures faster lookups. Think database indexing.

Red-Black Trees are favored in scenarios where insertions and deletions happen more frequently, as they offer a good balance between lookup, insertion, and deletion times due to their more relaxed balancing criteria.

Wrapping Up

Binary trees are integral to software development.

They provide an essential building block for developing efficient algorithms and programs. Their structured nature simplifies complex data management challenges, enabling engineers to tackle a wide range of computational tasks with greater efficacy.

Reverse Proxy vs Load Balancer — What’s The Difference (Recap)

• Load balancers are concerned with routing client requests across multiple servers to distribute load and prevent bottlenecks. This helps maximize throughput, reduce response time, and optimize resource use.

• A reverse proxy is a server that sits between external clients and internal applications. While reverse proxies can distribute load as a load balancer would, they provide advanced features like SSL termination, caching, and security. Reverse proxies are more concerned with limiting and safeguarding server access.

• Whilst load balancers and reverse proxies possess distinct functionalities, in practice the lines can blur, as many tools act as both a load balancer and reverse proxy.

For an extended explanation of the differences between a load balancer and a reverse proxy, see the full post here.

Data Structures Real-world Examples

• ListList: Online shopping cart — an ordered collection of items with the ability to access items at specific positions.

• Linked List: Browser history — enables quick and efficient traversal backward and forward through the history.

• Hash Table: Caching — Many caching algorithms, like in web browsers and content delivery systems, use hash tables to quickly look up values based on a key.

• Stack: Undo functionality — Last In, First Out (LIFO) the last element added is the first one to be removed.

• Queue: Printer queue — follows the First In, First Out (FIFO) principle, print jobs are processed in the order they are received.

• Graph: Social media network — helps in suggesting new friends, finding mutual connections, and disseminating posts through the network.

• Matrix: Pathfinding — utilizes a two-dimensional array to represent a grid and determine the shortest path from one point to another.

• Tree: File system — trees are hierarchical in nature, mirroring the organizational structure of directories and subdirectories. Many file systems are represented as trees with directories as nodes.

• Heap: Priority queue — efficiently ensures that the element with the highest priority is always readily accessible.

Database Indexing Explained (Recap)

A database index is a lot like the index on the back of a book. It saves you time and energy by allowing you to easily find what you're looking for without having to flick through every page.

Database indexes work the same way. An index is a key-value pair where the key is used to search for data instead of the corresponding indexed column(s), and the value is a pointer to the relevant row(s) in the table.

To get the most out of your database, you should use the right index type for the job.

• B-tree — One of the most commonly used indexing structures where keys are hierarchically sorted.

• Hash index — Best used when you are searching for an exact value match. The key component of a hash index is the hash function.

• Bitmap Index — Very effective in handling complex queries where multiple columns are used.

• Composite Index — May be used when multiple columns are often used in a WHERE clause together.

Indexing can be a double-edged sword. It significantly speeds up queries, but it also takes up storage space and adds overhead to operations.

See the full post here for a more comprehensive explanation.

That wraps up this week’s issue of Level Up Coding’s newsletter!

Join us again next week where we’ll explore caching eviction strategies, the main components of docker, and how SSO (single sign-on) works.