# Introduction to Binary Tree

### 1\. What is Binary Tree?

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1690723436564/393501c7-7e6d-48b7-98c6-335c1e7db1e0.png align="center")

A **binary tree** is a tree-type non-linear data structure with a maximum of two children for each parent. Every node in a **binary tree** has a left and right reference along with the data element. The node at the top of the hierarchy of a tree is called the root node. The nodes that hold other sub-nodes are the parent nodes.

A parent node has two child nodes: the left child and the right child. Hashing, routing data for network traffic, data compression, preparing binary heaps, and binary search trees are some of the applications that use a binary tree.

### 2\. Terminologies related to a Binary Tree

* **Node:** A node is a basic unit of a data structure, such as a linked list or tree data structure. Nodes contain data and also may link to other nodes.
    
* **Root:** A tree’s topmost node.
    
* **Parent:** Each node (apart from the root) in a tree that has at least one sub-node of its own is called a parent node.
    
* **Child:** A node that straightway came from a parent node when moving away from the root is the child node.
    
* **Leaf Node:** These are external nodes. They are the nodes that have no children.
    
* **Internal Node:** As the name suggests, these are inner nodes with at least one child.
    
* **Depth of a Tree:** The depth of a node in a binary tree is the total number of edges from the root node to the target node. Similarly, the depth of a binary tree is the total number of edges from the root node to the most distant leaf node.
    
* **Height of a Tree:** It is the number of edges from the node to the deepest leaf. The tree height is also considered the root height.
    

### 3\. Types of Binary Tree

* **Full Binary Tree:** A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children.
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1690723589155/ba83475f-f894-45df-a59c-aa8147701aca.png align="center")
    
* **Complete Binary Tree:** A complete binary tree is just like a full binary tree but with the following major differences-
    
    1. Every level must be completely filled
        
    2. All the leaf elements must lean towards the left.
        
    3. The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.
        

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1690724191868/70a4d9c5-72df-4923-b03c-f01a79529466.png align="center")

* **Perfect Binary Tree:** A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1690724269515/91106c5c-daed-4ed1-a886-b5861b148e57.png align="center")

* **Balanced Binary Tree:** It is a type of binary tree in which the difference between the height of the left and the right subtree for each node is either 0 or 1.
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1690722576476/d0d5d5e8-1adc-49bf-9d4d-9b7e37be3af6.png align="center")
    
* **Degenerate or Pathological Binary Tree:** A degenerate or pathological tree is a tree having a single child either left or right. This means that the tree will behave like a linked list data structure.
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1690723021117/99289663-cdf9-4194-bd38-842c44144d85.png align="center")
    

*Interesting Fact: The height of a Degenerate Binary Tree is equal to the total number of nodes in that tree.*

* **Skewed Binary Tree:** A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left nodes or the right nodes. Thus, there are two types of skewed binary tree: **left-skewed binary tree** and **right-skewed binary tree.**
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1690723330791/800d1d99-dd8c-47d7-85f8-d0bd7c55156b.png align="center")
    

In the [next blog](https://safiulkabir.com/basic-operations-on-a-binary-tree), we'll discuss the basic operations of a binary tree.