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)