Everything you need to know about Binary tree data structure
Binary tree data structure is a very useful data structure. It is a common topic in coding interviews. In this blog, you will learn everything you need to know about Binary tree data structure.
Why does Binary tree data structure exist?
- Stores the data in sorted order.
- Easy to find nodes with binary search algorithm with O(logN) complexity.
If you don't know anything about trees, please read the following blog:
Everything you need to know about Binary tree data structure
So,
What is a Binary tree?
A Binary tree is a tree where a parent node can have at most 2 children. It can have 0 children but it will never have 3 children or more. Let's see a picture.
You can see that none of the parent nodes have more than 2 children. They have 0-2 children.
Invalid tree:
That is condition 1.
Condition 2 is:
- Every left child value will be less than the parent value.
- Every right child value will be greater than the parent value.
You can see that every parent and their children are maintaining the above condition.
What about duplicate values?
Now, it is up to you. You can allow duplicate values in the tree. If so, then you will add them to your left or right side.
What should a node contain?
A node will contain 3 data.
- Left child node reference.
- Right child node reference.
- Actual value.
If a parent has no child or has only one child then the reference value will be null.
Properties of Binary tree
- The maximum number of nodes at level 'l' of a binary tree is 2^l.
If you don't know about the levels of the height of a tree please read the blog about trees.
- The maximum number of nodes in a binary tree of height 'h' is 2^h – 1.
- The minimum number of nodes in a binary tree of height 'h' is h+1
There are some variations of binary trees. They are :
- Full binary tree.
- Perfect binary tree.
- Complete binary tree.
- Balanced binary tree.
I will talk about them on other blogs.
Shameless Plug
Want to create your own blog? Well, I am creating a video series where you will learn about how to create a JAMstack blog with Nextjs and Chakra-UI.
Lessons
- Intro & Setup
- Build Homepage UI
- How our app will work
- MDX, MongoDB, Static Homepage
- Generate Static Blog Page
- Style Blog page with Chakra-UI and MDX-embed
- Build a real-time view counter
- Autocomplete search form with MongoDB Atlas Search Index
- Deploy application to Vercel
Demo
You can demo the website from here
Features
- Static Blog pages will make the website load faster.
- Blogs will have code blocks with syntax highlighting and many embed components like youtube videos, GitHub gist, Tweets, and so many other things.
- Autocomplete search feature for the blog posts.
- Real-time view counter and so on.
Please like and subscribe to Cules Coding. It motivates me to create more content like this.
That's it for this blog. I have tried to explain things simply. If you get stuck, you can ask me questions.
By the way, I am looking for a new opportunity in a company where I can provide great value with my skills. If you are a recruiter, looking for someone skilled in full-stack web development and passionate about revolutionizing the world, feel free to contact me. Also, I am open to talking about any freelance project. I am available on Upwork
Contacts
- Email: thatanjan@gmail.com
- LinkedIn: @thatanjan
- Portfolio: anjan
- Github: @thatanjan
- Instagram (personal): @thatanjan
- Twitter: @thatanjan
- Upwork: @thatanjan
Blogs you might want to read:
- Eslint, prettier setup with TypeScript and react
- What is Client-Side Rendering?
- What is Server Side Rendering?
- Everything you need to know about tree data structure
- 13 reasons why you should use Nextjs
- Beginners guide to quantum computers
Videos might you might want to watch: