Trees, Binary Search Trees and traversal methods, the difference and why.

Data structures, amongst other things, are used to store and organize data. Different types of data are more efficiently organized using particular data structures.

Trees are non-linear data structures which are quite often used to represent hierarchical data such as the employee organizational structure in a company.

Structure of a Tree

A tree is a collection of entities called nodes (represented as circles in our diagrams) are linked together with an edge to simulate a hierarchical structure. Each node contains data that can be of any type as long as all the nodes contain the same type of data.

Components of a Tree

Root: A node with no incoming link to another node, i.e. no parent.

Child: A node with an incoming link from an upper node, i.e. a parent node. A child can only have one parent.

Parent: A node with an outgoing link to a lower node, i.e. a child node. A parent can have multiple children.

Siblings: Children nodes with the same parent.

Leaf: A node with no outgoing link to a lower node, i.e. no child node.

Many different types of trees exist which are optimized for particular use-cases. Each tree type offers its own particular structure. Some commonly used trees include:

  • Binary Trees

For the purpose of this blog, we will take a deeper dive into Binary Search Trees and traversal methods.

As we now know, trees are one of the most fundamental data structures. They are used to store and organize data.

A binary tree is a tree data structure composed of nodes, each of which has at most, two children, referred to as left and right nodes. The tree starts off with a single node known as the root.

Each node in the tree contains the following:

  1. Data

In the case of a leaf node, the pointers to the left and right child point to null.

Note: There is no specific way to arrange data in a binary tree.

Common operations

Let’s look at a list of common operations that can be performed on a binary tree.

Insertion

Elements may be inserted into a binary tree in any order. The very first insertion operation creates the root node. Each insertion that follows iteratively searches for an empty location at each level of the tree.

Upon finding an empty left or right child, the new element is inserted. By convention, the insertion always begins from the left child node.

Deletion

An element may also be removed from the binary tree. Since there is no particular order among the elements, upon deletion of a particular node, it is replaced with the right-most element.

Tree traversal

Another frequently used tree operation is traversal. Tree traversal is the process of visiting each node present in a tree. There are three methods of tree traversal:

  1. In-order traversal (Left -> Root -> Right)

In-order

In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal can be used.

If a binary tree is traversed in-order, the output will produce sorted key values in ascending order.

Pre-order

Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expression on of an expression tree

Post-order

Postorder traversal is used to delete the tree. Postorder traversal is also useful to get the postfix expression of an expression tree.

Binary trees are one of the most efficient and frequently used data structures. They represent structural relationships in data and are used to represent hierarchies.

I hope that this post made understanding Binary trees and use-cases a tad bit easier.

Happy coding :)