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
- Binary Search Trees
- AVL Trees
- Red-Black Trees
- 2–3 Trees
- 2–3–4 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:
- Data
- Pointer to the left child
- Pointer to the right child
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:
- In-order traversal (Left -> Root -> Right)
- Post-order traversal (Left -> Right -> Root)
- Pre-order traversal (Root -> Left -> 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 :)
