Hi, this the part 2 of the tree in the data structure, we're going to talk about binary tree and its famous types.
Definition of binary tree
Binary tree: is one of the most famous tree data structure which each node should have at most 2 children (left child and right child), in this type of trees, all nodes contains three items which are data, pointer to left child, pointer to right child.
Types of binary tree
Full Binary tree
- In this type of trees, all nodes except the leaves have two children
Perfect Binary tree
- All internal nodes have exactly two children and all the leaves are at the same level.
Degenerate binary tree
- In This kind of tree, all nodes have only one child.
Complete Binary tree
- Like a full binary tree, All levels are filled, but All the leaves should lean towards the left
Balanced Binary tree
- the absolute value of the height difference between the left and the right subtree is smaller than or equal 1.
| height(left_sub_tree) - height(right_sub_tree) | <= 1
Skewed Binary tree
- All nodes have only one child except the last one (leaf) which hasn't a child. It divided into two types: left skewed binary tree and right skewed binary tree
References and useful Resources
- https://www.geeksforgeeks.org/binary-tree-data-structure/
- https://www.programiz.com/dsa/binary-tree
- https://www.programiz.com/dsa/perfect-binary-tree
- http://www.cs.kent.edu/~durand/CS2/Notes/10_Binary_Trees/ds_treesB.html
- https://www.programiz.com/dsa/balanced-binary-tree
- https://www.journaldev.com/43957/balanced-binary-tree-check
- https://www.programiz.com/dsa/complete-binary-tree
Top comments (0)