If you’ve taken a data structures course in your computer science degree, or are a self-taught programmer, chances are you’ve come across the term “Binary Trees”. Although they may sound a bit overwhelming and complex, the concept of a binary tree is quite simple.
Read on as we dissect binary trees, and why they are a necessary core concept for programmers.
What Are Binary Trees?
Binary trees are among one of the first data structures that students are taught in a data structures course. A binary tree is made of many nodes, and each node of the binary tree contains two pointers that indicate the left and right child data nodes.
The first node in a binary tree is called the “root”. Nodes of the last level in a tree are called leaves.
Each node contains a data item and two node pointers. An empty binary tree is represented by a null pointer. As you may have already figured out, binary trees can only have two children (hence the name).
Types of Binary Tree Structures
There are several different binary tree structures depending on the way the nodes are positioned. A binary tree is called a full binary tree when each node in the tree has either zero or two children. In a perfect binary tree, all nodes have two children and the leaves are all at the same depth.
A complete binary tree has nodes filled in every level, with the exception of the last level. In complete binary trees, nodes are concentrated on the left side of the root. Another common structure is a balanced binary tree; in this structure the heights of the right and left subtrees must differ at most by one. It is also required that the left and right subtrees must be balanced as well.
It's important to note that the height of the balanced binary tree is O(logn), where n is the number of nodes in the tree.
In some cases, if each node only has one left or right child, then the binary tree can become a skewed binary tree. It will then behave like a linked list, such trees are also called a degenerate tree.
What Are Binary Search Trees?
A binary search tree (BST) is essentially an ordered binary tree with a special property known as the "binary search tree" property. The BST property means nodes with a key value less than the root are placed in the left subtree, and nodes with a key value greater than the root are part of the right subtree.
The BST property must be true for each subsequent parent node in the tree.
Binary search trees offer quick insertion and lookup. Insertion, deletion and search operations have a worst-case time complexity of O(n), which is similar to a linked list.
Benefits of Binary Trees
Binary trees offer many benefits which is why they remain a very useful data structure. They can be used to show the structural relationships and hierarchies in a data set. More importantly, binary trees allow efficient searching, deletion and insertion.
It's also very easy to implement and maintain a binary tree. A binary tree offers programmers the benefits of an ordered array and a linked list; searching in a binary tree is as fast as in a sorted array and insertion or deletion operations are as efficient as in linked lists.
Binary Trees Are Important Data Structures
Binary Trees are a very important data structure and it's crucial that programmers are comfortable applying them in their programs. Often, interviewers ask simple binary tree problems such as traversals, maximum depth, mirroring, etc.
We highly recommend understanding the binary tree concept, and being familiar with typical interview problems.