DEV Community

Cover image for Elementary Data Structures with JavaScript - Binary trees - PART 1πŸš€
devlazar
devlazar

Posted on • Updated on

Elementary Data Structures with JavaScript - Binary trees - PART 1πŸš€

Table Of Contents
* πŸ€“ INTRODUCTION
* πŸ“œ DEFINITION
* πŸ‘¨πŸ»β€πŸ”¬OPERATIONS
* πŸƒπŸ»β€β™€οΈTRAVERSAL EXPLANATION
* πŸ™ THANK YOU

πŸ€“ INTRODUCTION

Welcome, my dear hackers!πŸš€ Welcome to yet another blog article about elementary data structures.

If you missed the previous article where we describe the Linked Lists and write pseudocode, you can check it out here:

Today, we are going to start a three-part article about Binary Tree data structure. We will talk a bit about theoretical stuff because it will make sense of all the implementation that we will do using the JavaScript programming language. As you may know, data structures are not specific to any programming language, so you are free to use any other programming language of your choice.

Please feel free to connect with me via Twitter, Instagram or LinkedIn

Let's start our journey!
journey

πŸ“œ DEFINITION

Binary tree is an ordered "tree" where each node has two "children" nodes at most.

  • Right child and Left child

A subtree of some node N is called the left and right subtrees, and the node N is their parent. This is also known as the Knut's binary tree.

A Strict binary tree is a binary tree where each node has 0 or 2 subtrees.

Complete binary tree is a strict binary tree of a height h where all the leaves are at the level h.

A Leaf is a node that has no children nodes.

A total number of nodes in a complete binary tree of height h is:

  • n=2h+1 - 1

A height of a tree made up of n nodes is:
h = log2(n+1)-1

An almost complete binary tree is a tree where all of the levels, except the last one, filled out entirely.

A balanced tree is a tree where the height of the left and right subtree differs only by one.

πŸ‘¨πŸ»β€πŸ”¬ OPERATIONS

Primitive operations

  • πŸ“„ Get the content of the node N
  • πŸ‘ˆπŸ» Get the left child of the node N
  • πŸ‘‰πŸ» Get the right child of the node N
  • πŸ‘ͺGet the parent node of the node N
  • πŸ§’πŸ»πŸ‘ΆπŸ» Get the sibling node of the node N
  • ➑Check if the node N is a right child
  • β¬…Check if the node N is a left child

Composite operations

  • πŸƒπŸ»β€β™€οΈ Binary tree traversal
  • 🌎Creating the binary tree
  • πŸ“₯Insert into a binary tree
  • ❌Delete a node from the binary tree
  • πŸ”ŽSearch an element in the binary tree
  • πŸ”Merging two binary trees

πŸƒπŸ»β€β™€οΈ TRAVERSAL EXPLANATION

There are a couple of ways to traverse a tree:

PREORDER

  • Process the root node
  • Traverse the left subtree
  • Traverse the right subtree

POSTORDER

  • Traverse the left subtree
  • Traverse the right subtree
  • Process the root node

IN-ORDER

  • Traverse the left subtree
  • Process the root node
  • Traverse the right subtree

BY LEVEL TRAVERSAL

  • Traverse all of the nodes by levels, starting from the node 0 a.k.a. the root node.

We will write minimal pseudocode for our traversal algorithms:

PREORDER TRAVERSAL

1 preOrder(root):
2    visit(root) //print out the content
3    preOrder(left(root))
4    preOrder(right(root))
5 exit procedure
Enter fullscreen mode Exit fullscreen mode

POSTORDER TRAVERSAL

1 postOrder(root):
2    postOrder(left(root))
3    postOrder(right(root))
4    visit(root)
5 exit procedure
Enter fullscreen mode Exit fullscreen mode

IN-ORDER TRAVERSAL

1 inOrder(root):
2    inOrder(left(root))
3    visit(root)
4    inOrder(right(root)) 
5 exit procedure  
Enter fullscreen mode Exit fullscreen mode

BY LEVEL TRAVERSAL

//for this purpose we need to use the helper - the queue data //structure
1 levelOrderN(info, left_link, right_link, root)
2    pointer => root
3    while (pointer not equal to null)
4      visit(pointer)
5      //add all of the descendants into a FIFO queue
6      queue_enqueue(left(pointer))
7      queue_enqueue(right(pointer))
8      //read from a queue
9      pointer => queue_dequeue()
10     //if the queue is empty dequeue returns null
11   endwhile
12 exit procedure
Enter fullscreen mode Exit fullscreen mode

πŸ™ THANK YOU FOR READING!

We are taking baby steps! The binary trees are a bit more complex data structure, so we would need to break this article in order for you (and me πŸ˜†) to not freak out. Stay tuned for the next chapter of this article!

References:
School notes...
School books...

Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!

β˜• SUPPORT ME AND KEEP ME FOCUSED!
Buy Me a Coffee at ko-fi.com

Have a nice time hacking! 😊

Top comments (0)