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.

  1. Full binary tree: each node has exactly either 0 or 2 children, but never just one child
  2. 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.
  3. Perfect binary tree: when all levels including the last level are full with nodes
Graphic of full, complete, and perfect binary trees

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.

Graphic comparing a balanced and non-balanced binary 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:

--

--

Software Engineer | Flatiron School Alum | Dancer | Looking for Work!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Esther 승연 Kang

Software Engineer | Flatiron School Alum | Dancer | Looking for Work!