A binary tree is a type of tree data structure. If every node in a tree has 0, 1, or 2 child nodes, it is known as a binary tree.
Here we will discuss two types of binary trees.
- Full binary tree
- Perfect binary tree
Full binary Tree
A full binary tree is a binary tree, where every node has 0 or 2 children.
Perfect Binary Tree
A perfect binary tree is a tree where every node has 0 or 2 children. And the level of each leaf node is the same.
There is a formula to calculate the number of nodes at each level in a binary tree.
Number of a node in each level = 2 ^ levelLevel 0 = 2 ^ level = 1 nodeLevel 1 = 2^ 1 = 2 nodeLevel 2 = 2 ^ 2 = 4 nodeLevel 3 = 2^ 3 = 8
Calculate big O of perfect binary tree
Now let’s calculate the big O of a binary tree.
No. of nodes = 2 ^ h — 1 [h = height]
We will drop -1. Because we drop the constant while calculating Big O.
So,
Nodes = 2 ^ hLog nodes = height
In case you are wondering how logs work
Log 100 = 210 ^ 2 = 100
Based on height, the time complexity for a node will be logN.
Suppose we are looking for node 8.
We will search from the root node. We check if the root node is node 8. It is not.
So, now we have to make a choice, to search in the left node or right node.
Suppose, we choose the left node. Now, we check if 2 is the node we are looking for. It is not. Then, we can now again make a choice to choose the left and right child node. Suppose we choose the right node which is node 8. It is the node we are searching for. Now, our search is completed in 3 steps. Instead of searching in all nodes. So, O(logN) is an efficient time complexity.