Making sense of the Binary Search Tree

I grew up adjacent to software engineering, but never really full immersed in it. I learned HTML and CSS in middle school, I learned how to use the command line in highschool, and I thought myself how to program microcontrollers in college. I would call myself software savvy, but certainly no expert. That’s why I’m having such a hard time learning data structures. Being a self-taught programmer for most of my life, I had no foundational education in some of the more abstract parts of coding, particularly things like trees. In an effort to understand it more deeply, here’s my attempt at an explainer…

What is a tree?

A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.

The tree is generally represented in a top-down configuration like in this image. The top node is the root, and each of the nodes that sprout from the root are its children. This is also true for each of the children, each child is a node, and therefore can have children of its own.

Any node (apart from the root) that has children is known as an internal node (also called and inode or branch node), and an external node (can also be called a terminal node or leaf node) has no children. An edge (or link) connects nodes together. The height of a node is the length of the longest path between that node and an external node. The depth of a node if the length of the path between the node and its root.

Binary Search Tree

A Binary Tree is a tree data structure where each node has at most two children, which are referred to as the left child, and the right child. Also, whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.

Binary Search Trees support three main operations: Search, Insertion, and Deletion

Searching

Insertion

Deletion

Writing this has really help solidify this conceptually for me. That being said, I’m still going to need a lot of practice before I can write one of these functions off the top of my head. Hopefully this will serve as a good starting point for my junior dev peers.

I take things apart, and then I put them back together again