In this post, we will look at the **binary tree** data structure. We will see the different trees and their characteristics.

## Introduction

A* binary tree data structure* is a hierarchical data structure where each element have maximum 2 children. We call these children as left and right child. In the following example, the left side tree is a binary tree while the right one is not.

In the right tree structure, we have over 2 child nodes for the parent node 2. Let’s look at some points for the binary tree.

- Each node contains a pointer to the left and right sub-tree.
- Each node contains a data element.

[pullquote align=”normal”]If a tree has only 1 node, it’s also aÂ binary tree. [/pullquote]

[pullquote align=”normal”]Nodes in the example images are only labeled and they do not represent the number/data for the tree [/pullquote]

## 2. Binary Tree Terminologies

Before we get in details of the* binary tree data structure*, let’s refresh some common terminology.

- Root node: – The topmost node is the root node (node 1 is the root node).
- We define a tree by parent and child nodes.
- Parent Node: Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node called as a parent.
- Leaf Nodes: Nodes which do not have any child nodes.
- Height: The height of a tree is the maximum number of edges from the node to the farthest leaf node.
- Depth: Number of edges from the root node to the node.
- Size: Size of a tree is the total number of nodes it contains.

## 3. Types of Binary Trees

Before we get in to other details, let’s discuss the different types of the tree. I will cover the most popular tree structures.

### 3.1 Full Binary Tree

A * full binary tree* is a tree with every node has either 0 or 2 children. No node will have only one child.

### 3.2 Complete Binary Tree

A tree where every level fully filled (have 2 children) except maybe the last level. For the * complete binary tree*, we fill the last level from left to right.

### 3.3 Perfect Binary Tree

A * perfect binary tree* is both complete and full.All the leaves have the same depth or same level.

[pullquote align=”normal”]A perfect tree is very rare. [/pullquote]

## 4. Binary Tree Traversal

*Tree traversal* is the process to visit all nodes. On a high level, we can group the tree traversal in the following 2 groups.

- Depth-first traversal.
- Breadth-first traversal.

For the breadth-first traversal, we visit the nodes of the tree by levels from top to bottom and left to right. For the depth-first traversal; we have the following main traversal options (Also look at the following tree for the sample output)

### 4.1 In-Order Traversal

For the In-Order traversal, we visit the left branch then current node and finally the right branch of our tree. If we perform the * In-Order traversal on a binary search tree*, we get the data in ascending orders. Here is the screen shot outlining the in-order traversal.

[pullquote align=”normal”]Number shows the traversal sequence in the tree [/pullquote]

Output:Â Â Â `9, 5, 1, 7, 2, 12, 8, 4, 3, 11`

### 4.2 Pre-Order Traversal

In the pre-order tree traversal, we visit the current node then left tree and finally the right tree. Here is the screen shot outlining the in-order traversal.

Output:Â `8, 5, 9, 7, 1, 12, 2, 4, 11, 3`

Â

### 4.3 Post-Order Traversal

With post-order traversal, we visit the left tree then right tree and finally the parent. Let’s see how the traversal sequence looks like:

Output: `9, 1, 2, 12, 7, 5, 3, 11, 4, 8`

## 5. Binary Search Trees

A ** binary search tree** is a specialized tree which fulfills the following properties:

- Each node contains certain data.
- The data in the left sub-tree is always less than the parent node.
- Data on the right sub-tree is always greater than parent node.

[pullquote align=”normal”] Some definition allows duplicates in the binary search tree while some don’t allow duplicate keys in BST. Both definitions are correct. [/pullquote]

## 6. Balanced Vs Unbalanced Binary Tree

Two binary search trees can store the same values in different ways:

Balanced tree is a tree where

- The left and right sub-trees’ heights differ by at most one.
- The left sub-tree is balanced.
- The right sub-tree is balanced

## 7. Time Complexirty BST

Â | Average |
Worst |

Space |
$O(n)$ | $O(n)$ |

Insert |
$O(lg(n))$ | $O(n)$ |

Search |
$O(lg(n))$ | $O(n)$ |

Delete |
$O(lg(n))$ | $O(n)$ |

## 8. BST Pros and Cons

Let’s cover some strengths and weaknesses of a BST:

- Efficient for insertion and deletion operations.
- As compared to sorted arrays, insertion and deletion are faster ($O(lg(n))$ for BSTs, O(n) for arrays).
- We can do element insertion in sorted order in O(n).
- Binary search tree can lead to poor performance if we do not balance the tree.
- They do not have any O(1) for any operation.

## Summary

In this post, we covered the * binary tree* and

**binary search tree**data structure. We talked about various types of a tree and what are the

**. At the end of the post we checked the**

*different tree traversal techniques**.*

**binary search tree and its time complexities**