Introduction to the Binary Tree

About Binary Trees

A binary tree is a hierarchical data structure unlike other data structures like arrays that are linear. A real world application of something a binary tree resembles is… well… a family tree.

A binary tree uses nodes instead of elements. Each blue circle you see above is a node. A binary tree starts with a head honcho just like a family tree. This node at the top is called the root node. To keep the family tree analogy going nodes are referred to as parents, children, siblings, and grand children which keeps things simple and relatable. In the example above the parent node is the root and it will have a left and right child. The 2 children are considered siblings to each other.

Why use a binary tree?

• Store information that naturally forms a hierarchy like the file system on a computer, data on relationships, or many other things.
• Trees provide moderate speed of searching (quicker than a linked list and slower than arrays)
• Trees provide moderate insertion/deletion (quicker than Arrays and slower than unordered linked lists).
• Unlike Arrays, trees don’t have an upper limit on number of nodes as nodes are linked using pointers (the lines you see connecting nodes).

A further look into the structure

It is important to note that trees can only expand out in one direction. Nodes in a binary tree have a maximum of 2 children making the name “binary” tree appropriate. If a node does not have any children it is called a leaf node.

Binary Search Tree

Often when we talk about binary trees, we want to utilize a binary search tree. Binary search trees. Traversing through binary search trees is incredibly fast cutting down data you have to look though significantly.

To classify as a binary search tree (BST) a tree needs to follow some rules.

1) Each node of a BST may only have exactly 0, 1, or 2 children.

2) For each node, all nodes in its left subtree have a value less than the parent. The inverse is also true.

3) Both the left and right subtrees of a parent must also be BSTs.

Traversing through a binary search tree

The reason binary search trees are so fast is you traverse through an organized structure, not needing to check every single node. For example, If we wanted to add a 17 to the above image we would walk down the branches and look left and right to solve this issue.

• To insert the 17, we would start at the root 30. 17 is less than 30 so we are going to go to the left child of 30.
• We are now standing on 20 and 17 is less than 20. Like before want to go to the left.
• We have reached 10 and for once 17 is greater than 10 so we will move to the right child.
• Finally we have reached 15 which is a leaf node (has no children). 17 is larger than 15 so we want to insert it as the right child of 15 and that is where it will stay.

Searching through the tree is the same exact process! If you look back to the image we didn’t even have to look at any nodes to the right of 30 or any nodes to the right of 20. This can cut down speeds of insertion, searching, and deletion dramatically ( O(log n) ).

Types of traversals

There are 3 different ways to traverse through a tree.

Pre-order: start with the root then visit left child then right child.

In-order: start with the left child, go up to the parent then down to the right. This will print numbers in order.

Post-order: start with left child then right child then finish on the root.

Final thoughts

Binary search trees are very interesting because of the speed in which you can find data as opposed to other data structures. I have enjoyed looking into the basics and theory behind this data structure and look forward to implementing it into my projects and algorithm problems as I learn more about them.