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:
Article No Longer Available
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!
📜 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
POSTORDER TRAVERSAL
1 postOrder(root):
2 postOrder(left(root))
3 postOrder(right(root))
4 visit(root)
5 exit procedure
IN-ORDER TRAVERSAL
1 inOrder(root):
2 inOrder(left(root))
3 visit(root)
4 inOrder(right(root))
5 exit procedure
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
🙏 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!
Have a nice time hacking! 😊
Top comments (0)