Data Structure Trees vs Binary Trees
What is tree ?
Trees are very important data structures that collection of nodes just like the linked lists. The differences with linked lists and trees is that trees has parent and child relationships.
The meaning of tree is about the structure of a Binary tree. Basically there are some parent nodes that have some child nodes that give us the direction to reach data easier and faster. Binary Tree structure looks like a tree. This is the reason we call them trees. You can think of a big tree which has many branches and lit splits at some point and they can keep splitting. If our target is the getting specific apple belonging to one specific branch we have to follow and hold the branch of that tree to get that specific apple.
As mentioned in the example above we need trees to create our data structure for inserting or removing data(etc) with stacks or queues. Trees giving us abilities to do all this operation faster and easier.
Let’s dive in and see what is the advantage of trees ;
As you see each of these circles represent a node like in the linked list. But as you notice it’s different than linked list.
Each node can have more than one reference than another node.
If you see the diagram we have one top node(1) and its reference to another node(2) ,(3) and(4). Those nodes also reference one or more nodes as well. Each node could have any number of child nodes. There are no real rules about how many in a generic tree. There are some restrictions for binary trees which we will look at it after.
The most important thing about trees is they are nonlinear. They can have branches. You can have more than one pathway through a tree . The lists are linear.
Tree Terminology
Root: Top node of the tree
Child: A node directly connected to another node when moving away from the Root.
Parent: The converse notion of a child
Siblings: A group of nodes with the same parent
Leaf: A node with no children
Edge: The connection between one node and another
Binary Search Trees
As in the real world there are many kinds of trees. It’s the same for data structure trees as well. There are many varieties in the world of computer science data structure of trees. But I will dive into Binary Tree in this article. When we store sorted data in a particular way, the Binary Search Tree makes it easier to retrieve. I mentioned earlier that Binary Tree has some restrictions. Each node can have at most two children at the Binary part. It can have (0 )children , (1) children and (2) children. But it can’t have (3) children. Because Binary trees have some special properties that make them easier to navigate.
Binary Search Trees are sorted in a particular way they are kept in an order. Binary Search Tree used to store that can be compared. It could be strings or any other data type has some way to compare and make it in order depending on the value. If the value is greater or less than the parent node. That would give us direction to proceed and reach the desirable node. Basically this is how they work.
How are we gonna move in Binary Search Tree
If you check the diagram you can see our root node on the top of the tree. Anything less than the root node would be placed on the left side. Anything greater than root would be located the right. You can repeat that on each child node.
How Binary Search Trees Work?
- Every parent node has most two children
- Every node to the left of a parent node is always less than the parent
- Every node to the right of a parent node is always greater than the parent
Another Example
This Binary tree is larger than the first diagram. We take any node like the root all nodes left. All nodes on the left should be less than root(41). If we go one level down and see node(20). The right node of parent node(29) is larger than parent. The node on the left(11) is less than the parent node. As you see, other nodes are also implemented based on this logic.
This rule makes Binary Search tree rather than binary tree. Data is kept in a particular order every node child to the right is greater than a parent node, every piece of data to the left is less than parent node.
Binary Search Tree Class
As you remember how we implemented classes for Linked List . We had the Link List class then we had a node class. If you are not familiar with classes you can read my singly linked list blog and you can learn about it.
Implementing Binary Search Tree classes different than a Linked List classes.
Binary Search Tree has one important property which is root.
class BinarySearchTree{
constructor(){
this.root = null;}
Node Class
Each node has a value but instead of .next or .previous in Linked List we have left and a right pointer.
class Node {
constructor(value){
this.value = value;
this.right = null;
this.left = null;
}
}