Types of Binary Tree [DSA-2022]
- Full Binary Tree A Binary Tree is a full binary tree if every node has 0 or 2 children. We can also say a full binary tree is a binary tree in which all nodes except leaf nodes have two children.
2. Complete Binary Tree: A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible
3. Perfect Binary Tree A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes are at the same level.
The following are examples of Perfect Binary Trees.
4. Balanced Binary Tree
A binary tree is balanced if the height of the tree is O(log n) where n is the number of nodes. For Example, the AVL tree maintains O(Log n) height by making sure that the mod of the difference between the heights of the left and right subtrees is at most 1.
5. A degenerate (or pathological) tree A Tree where every internal node has one child. Such trees are performance-wise same as the linked list.
Summary:-
Thanks for reading…..
