Binary Tree

In our last episode, we learned about generic tree data structure. In this episode, we are going to learn about the below things on the Binarya Tree

1) What is Binary Tree Data Structure?

2) Architecture and Characteristics?

3) Run Time Complexity Summary?

So, let's get started,

Back in my college days, when I was reading about Trees, I got this question: Why are there so many Tree types? After getting the real-time experience, I got an answer to my question now, i.e., Trees aren't naturally organized. When we use a tree, we know what the overall structure looks like (basically a hierarchy), but we don't know where a specific element will be in the Tree hierarchy, not knowing the location of the element which we would like to operate on, makes our operation slow, so to accomplish our operation fast we can add some rules to the order of elements when generating Tree hierarchy. The nature of these rules classifies trees into distinct types, and Binary Tree is one of them.

1) Binary Tree

In a Binary Tree, the rule is that each node can have a minimum of zero and a maximum of two child nodes.

2) Architecture and Characteristics?

We have the following types based on the nature of the rules when generating a Binary Tree Hierarchy.

1. 1) Full Binary Tree

1.2) Perfect Binary Tree

1.3) Complete Binary Tree

1.4) Skewed Binary Tree

1.5) Balanced Binary Tree

1.1) Full Binary Tree: - The rule for the full binary tree is that every parent node/internal node has two or no children.

1.2) Perfect Binary Tree: - The rule for the perfect binary tree is that every parent / internal node has exactly two child nodes, and all the leaf nodes are at the same level.

1.3) Complete Binary Tree: -A complete binary tree is like a full binary tree but with only one significant difference. All Leaf Nodes must lean towards the left.

1.4) Skewed Binary Tree: - The rule for the skewed binary tree is that all nodes are either formed on the left or the right.

1.1.5) Balanced Binary Tree: - The rule for the balanced binary tree is that the difference between the height of the left and the right subtree for each node is either 0 or 1.

3) Run Time Complexity Summary?

References

1. Data Structures and Algorithms Made Easy in Java - Narasimha Karumanchi
2. https://www.bigocheatsheet.com/
3. https://www.udacity.com/course/data-structures-and-algorithms-in-python--ud513
4. https://www.diagrams.net/
5. https://www.javatpoint.com/binary-tree

Disclaimer

This article is governed by the "Fair Use" doctrine and is only for purposes such as criticism, comment & teaching.

Note: - This is a live article and subject to change.