# JavaScript Data Structures: Trees (pt. 2)

In the last blog post, I introduced the Tree data structure. We discussed the very basics — what trees look like and the different parts of a tree.

This week, I’ll talk about Binary Trees and the differences between a balanced tree and a non-balanced tree.

# Binary Trees

A binary tree is a tree where there is, at most, two children.

There are three types of binary trees.

**Full binary tree**: each node has exactly either 0 or 2 children, but never just one child**Complete binary tree**: when all levels*except*for the last level (in graphic below, level 2) are full with nodes — level 0 (where node 0 is) is full of nodes, but level 1 (where nodes 1 and 2 are) is not full with nodes because it is the last level.**Perfect binary tree**: when all levels*including*the last level are full with nodes

Keep in mind these following traits:

- A full tree is not always complete or perfect, but there are instances where a full tree can
**also**be complete*OR*perfect - A complete tree is not always full — some nodes can have one child, but a full tree, by nature, cannot have a node with one child, only 0 or 2. A complete tree can never be perfect.
- A perfect tree is always complete and full — each node has 2 children, but the last level has 0 children.

# Balanced vs. Non-balanced

When we’re looking at a non-balanced tree, we’re looking at a tree where one node has the majority of nodes — it essentially just looks like a line. It’s weighted too heavily on one side, nodes will have only one child, etc. It doesn’t even really look like a tree. So, in order to traverse the tree to find a value, it will take** O(n)** in terms of run time.

A balanced tree, however, has a more evenly distributed structure. It’s run time will be **O(log n)** because you doesn’t have to go through each node like you would in a non-balanced tree.

The amount of nodes you have to pass through in a balanced tree would be significantly less than in an unbalanced, where you have to pass through each individual node on the right side of the tree to get to that last child node.

And that’s it for this week! Fairly simple information, but very important for building and implementing trees.

Next week, I’ll be discussing how to implement a tree and traverse through it.

**Resources:**

- Tree Data Structures in JavaScript for Beginners by Adrian Mejia
- Both images found on Google