Trees
Tags: javascript, programming, tutorial, leetcode
Published: 2024-02-29 10:57:25

###Note
This is a summary of what I have learned in multiple courses, papers, articles, and learning from senior engineers. Trying to make it easier for the next person.
<br/>


![Binary Tree](https://media.giphy.com/media/v1.Y2lkPTc5MGI3NjExdzFwOWV6ZWQzbmdzMG04dTR2eDdzaWh0MGw4MW9iNmw0MnRqMTRldiZlcD12MV9pbnRlcm5hbF9naWZfYnlfaWQmY3Q9Zw/f6z5TkrTIBZILYOd1t/giphy.gif)

###Intro
Trees are something everyone that has some interaction with computer science hears about. Let's get into this.

**What is a Tree**

Tree is a collection of nodes in a specific order. It is non-linear. An example of a Tree, Binary Tree, is a tree with two children per node and each node only has one parent. There are a lot of different patterns for different trees but they are generally hierarchal.

** What are the different types of trees? **
1) Binary Tree
2) Binary search Trees
3) AVL Trees
4) N-Ary Tree
5) Red-Black Tree
And many more. These are the ones I have come across the most so these are the ones I want to cover

** What is a binary tree? **
Binary Trees are also a connection of nodes but they have specific rules. Since it is a BI-nary tree, each node only has two children and each node can only have one parent.

You can represent a binary tree pretty simply.

```javascript
class Node {
  constructor(key, left = null, right = null) {
    this.left = left;
    this.right = right;
    this.val = key;
  }
}

// Example usage: - Creating a sample binary tree
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

// The tree now looks like this:
//        1
//       / \
//      2   3
//     / \
//    4   5
```

Binary tree can be created like this or you can also create it by nesting the creation `new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));`. It seems a lot, but we are basically calling for the creation of node and pass other calls as arguments to the main call. 


Now that we know how to create a binary tree, we can talk about other parts like traversal.

There are three ways to traverse the tree. InOrder, PreOrder, and PostOrder


##Inorder
![InOrder Traversal](https://media.giphy.com/media/v1.Y2lkPTc5MGI3NjExNHd0cGllOHB1aDRiOWxqMWs1c2R4bWtnb3gyZG9qbWdpejV0dG9kMiZlcD12MV9pbnRlcm5hbF9naWZfYnlfaWQmY3Q9Zw/ofxx1r2udbVE9ks3aA/giphy.gif)
1) Left Sub Tree traversed
2) Root node visited
3) Right Sub Tree traversed
```javascript
function inorderTraversal(node) {
  if (node !== null) {
    inorderTraversal(node.left);
    console.log(node.val);
    inorderTraversal(node.right);
  }
}
```

##PreOrder
![InOrder Traversal](https://media.giphy.com/media/v1.Y2lkPTc5MGI3NjExOXQ0Ymxvd2t6cHo3M3A0MmNtc3c2bjY2bm15azd4d3Azc3NuNHFvcSZlcD12MV9pbnRlcm5hbF9naWZfYnlfaWQmY3Q9Zw/hS8d3pF2H1mNas1sZ7/giphy.gif)
1) Visit the root node
2) Traverse the left subtree
3) Traverse the right subtree
```javascript
function preorderTraversal(node) {
  if (node !== null) {
    console.log(node.val);
    preorderTraversal(node.left);
    preorderTraversal(node.right);
  }
}
```

##PostOrder
![InOrder Traversal](https://media.giphy.com/media/v1.Y2lkPTc5MGI3NjExaHQxOGU0a2R1ZGN4dTFhbmF5YXgwNG5zdWs5c200ZmxzanN6Y3p6MSZlcD12MV9pbnRlcm5hbF9naWZfYnlfaWQmY3Q9Zw/I2JWB7DalOVr4hX5kO/giphy.gif)
1) Traverse the left subtree
2) Traverse the right subtree
3) Visit the root node
```javascript
function postorderTraversal(node) {
  if (node !== null) {
    postorderTraversal(node.left);
    postorderTraversal(node.right);
    console.log(node.val);
  }
}
```

##BreadthFirst
![InOrder Traversal](https://media.giphy.com/media/v1.Y2lkPTc5MGI3NjExZ3I3anVxdTYxZ3hraHRhN3ZiOG51ZzNoY3pseThsNjJoYzd4ZDlnYiZlcD12MV9pbnRlcm5hbF9naWZfYnlfaWQmY3Q9Zw/FM5UK14OasO6IYq42u/giphy.gif)
We traverse the whole tree by rows. Start from the left most node to the right most node and then move to the next row
```javascript
function breadthFirstTraversal(root) {
  const queue = [root];

  while (queue.length > 0) {
    const currentNode = queue.shift();
    console.log(currentNode.val);

    if (currentNode.left) {
      queue.push(currentNode.left);
    }

    if (currentNode.right) {
      queue.push(currentNode.right);
    }
  }
}
```

Why do we need so many different traversals? What is the point of all of this? How do I apply this to leetcode? All this and much more in my next blog. 


See y'all there!