Member-only story
Introduction to Binary Trees
And other tree data structures in C
In computer science, a binary tree is an hierarchical data structure formed of nodes linked together. The first node is called the root, and every node can have up to two child nodes — one left and one right.
Alone, their use might seem limited, but when implemented as binary search trees or binary heaps, they offer quick ways of sorting and searching data. They’re also a great learning opportunity, because most functions used to implement them in C can involve recursion, pointer swapping, and other advanced, but fun, programming concepts. Let’s see how to implement them in C.
Binary Trees: Terminology
As mentioned in our introduction, binary trees are defined by a root node and children nodes, each node being able to have at most two children. There are a few keywords that we will need to know before we continue.
- Height — The height of a node is the maximum number of edges separating that node from a leaf (see leaf).
- Depth — The depth of a node is the number of edges separating that node from the root node.
- Size — The size of a tree is the number of nodes it contains.
- Balance — The balance factor of a node is the difference between the height…
