A tree is a non hierarchical data structure in which the the information or value is represented by Tree Nodes and these nodes are connected by Edges.
-
Node: A node is a entity which holds a value, an information, a pointer, etc.
- Internal Node: A node which has at least one child
- Leaf Node: A node which has no child or the last node in a tree branch
-
Edge: Edge is the link in between two nodes
-
Root Node: The entry point (usually represented by topmost node) of a tree is known as root node.
-
Height: Number of the edges in the longest path from root node to leaf node.
-
Degree: Degree of a node is the total number of branches of that node
Tree is of 4 types:
- Binary Tree
- Binary Search Tree
- AVL Tree
- B-Tree
To perform any operation or to get a specific value, tree traversal algorithms are used. We can traverse tree in basically three following types:
- Preorder Traversal
- Inorder Traversal
- Post Traversal
Here is an example of a tree which we are going to implement at last
First we need to create the JS class
$dy> class Tree {
$dy> // Tree defination will come here
$dy> }
A tree node contains value, left child and right child so let's go create that
$dy> class Tree {
$dy> constructor(nodeValue, leftNode, rightNode) {
$dy> this.value = nodeValue;
$dy> this.leftNode = leftNode;
$dy> this.rightNode = rightNode;
$dy> }
$dy> }
Assign default parameter as null if user doesn't pass the pointer to the left or right node
$dy> // Replace constructor signature with the following
$dy> constructor(nodeValue = 0, leftNode = null, rightNode = null)
Let's create a tree with three nodes
$dy> // we need not pass left or right as default parameter are already there
$dy> const left = new Tree('left');
$dy> const right = new Tree('right');
$dy> // here we need to pass the left and right node as parameter
$dy> const root = new Tree('root', left, right);
That's it, you have created the tree in above step and here is the complete code for a tree
$dy> class Tree {
$dy> constructor(nodeValue, leftNode, rightNode) {
$dy> this.value = nodeValue;
$dy> this.leftNode = leftNode;
$dy> this.rightNode = rightNode;
$dy> }
$dy> }
$dy> const node7 = new Tree(7);
$dy> const node6 = new Tree(6);
$dy> const node5 = new Tree(5);
$dy> const node4 = new Tree(4);
$dy> const node3 = new Tree(3, node6, node7);
$dy> const node2 = new Tree(2, node4, node5);
$dy> const root = new Tree(1, node2, node3);
Here is the JSON of the tree we just created
$dy> {
$dy> "value": 1,
$dy> "leftNode": {
$dy> "value": 2,
$dy> "leftNode": {
$dy> "value": 4
$dy> },
$dy> "rightNode": {
$dy> "value": 5
$dy> }
$dy> },
$dy> "rightNode": {
$dy> "value": 3,
$dy> "leftNode": {
$dy> "value": 6
$dy> },
$dy> "rightNode": {
$dy> "value": 7
$dy> }
$dy> }
$dy> }
- In searching algorithm, specially in heap sort
- HTML DOM is a tree
- Compilers uses the syntax tree to validate the syntax of a code