DEV Community

Cover image for Trees
Mohammed Shaikh
Mohammed Shaikh

Posted on • Updated on

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.

Binary Tree

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
Enter fullscreen mode Exit fullscreen mode

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
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);
  }
}
Enter fullscreen mode Exit fullscreen mode

PreOrder

InOrder Traversal
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);
  }
}
Enter fullscreen mode Exit fullscreen mode

PostOrder

InOrder Traversal
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);
  }
}
Enter fullscreen mode Exit fullscreen mode

BreadthFirst

InOrder Traversal
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);
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (1)

Collapse
 
wale1202 profile image
Wale1202

Good one