LUC #07: A User-Friendly Guide to Binary Trees
Making sense of binary trees and their role in programming
Level Up Coding
June 20, 2023
Welcome back to another edition of LevelUpCoding’s newsletter.
In today’s issue:
A deep-dive into Binary Trees
Principles of OOP (recap)
CDNs explained (recap)
What is NewSQL? (recap)
Read time: 4 minutes
Binary Trees: A Deep Dive
Last week we took a look at linear data structures and their best applications.
Now, let’s explore another data structure that helps make programs efficient — binary trees.
A binary tree is a tree data structure where each node has no more than two children.
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.
Binary trees are great for storing ordered data for sort and search operations. Their strict structure and properties make these tasks highly efficient.
Some typical use cases are:
Search algorithms
Sort algorithms
Pathfinding algorithms
Representation of hierarchical data
Classes are often used to implement binary trees because of their ability to use encapsulation and abstraction.
A Node class is used to store its value and its left and right child.
Node class example in Python
An insert function would be used to add a value relative to a given root node. Based on the binary tree type, it may need to travel through the tree to find its appropriate position.
Based on your use case, you may want to have other methods like search and traverse.
Binary trees are integral to programming.
They provide an essential building block for developing efficient algorithms and programs.
Principles of OOP
Encapsulation: group together related methods and properties while protecting the internal state.
Abstraction: hide implementation details to reduce complexity.
Inheritance: inherits properties and methods from other classes as a way to share logic.
Polymorphism: enables objects to change their form by extending or overriding existing methods.
CDNs explained
A content delivery network (CDN) is a network of geographically distributed servers that deliver web content to users based on their location.
CDNs reduce latency by storing a cached version of the webpage content on multiple servers. Content is delivered from the server closest to the user.
What is NewSQL?
NewSQL brings together the features of SQL and the scaling abilities of noSQL.
Some databases to get started:
Google cloud spanner
CockroachDB
VoltDB
SingleStore
That wraps up this week’s issue of LevelUpCoding’s newsletter!
Join us again next week where we’ll explore how to write efficient SQL queries, Python list methods, and effective debugging techniques.