Trees

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.

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.

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

1) Left Sub Tree traversed
2) Root node visited
3) Right Sub Tree traversed

function inorderTraversal(node) {
  if (node !== null) {
    inorderTraversal(node.left);
    console.log(node.val);
    inorderTraversal(node.right);
  }
}

PreOrder

1) Visit the root node
2) Traverse the left subtree
3) Traverse the right subtree

function preorderTraversal(node) {
  if (node !== null) {
    console.log(node.val);
    preorderTraversal(node.left);
    preorderTraversal(node.right);
  }
}

PostOrder

1) Traverse the left subtree
2) Traverse the right subtree
3) Visit the root node

function postorderTraversal(node) {
  if (node !== null) {
    postorderTraversal(node.left);
    postorderTraversal(node.right);
    console.log(node.val);
  }
}

BreadthFirst

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

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!

Comments

[Wale1202]

Good one