Trees and Binary Trees

What are trees?

Trees are a subset of graphs, a non-linear data structure, that provides an efficient way for searching and sorting. They are a collection of nodes and are a way to store information hierarchically.

What are binary trees?

Similar to regular trees, they have parent and child nodes that are connected in a hierarchical fashion.

A binary tree is a tree data structure in which each node has at most two child nodes, known as the left child and the right child. The topmost node in the tree is known as the root, and each child node can have its own subtrees, which are also binary trees.

In a binary tree, each node has a unique value, and the values in the left subtree of a node are less than the value of the node, while the values in the right subtree are greater than the value of the node. This ordering property makes binary trees useful for searching and sorting data.

Visualization of a Binary Tree

In this example, the node labeled 1 is the root node, while 8,9,10,11,13, and 14 are the called leaves, and the rest of the nodes are called internal nodes.

Some terminology:

What are the different types of binary trees?

Full tree -  tree where every node have two children except the leaves

Complete tree - every node has at least two children except for the bottom level, and they have to be filled in as far left as possible

Degenerate tree - every node only has one child node

Perfect tree - every internal node has two children and all leaves are on the same level

Balanced tree - height of the left and right subtree of any node differ by not more than 1

Different Types of Binary Trees

How do you traverse a binary tree?

For traversal of a binary tree, there are three different ways:


preorder: [1,2,4,6,3,5,7,8,9]

inorder: [6,4,2,1,3,7,5,9,8]

postorder: [6,4,2,7,9,8,5,3,1]

Breadth first traversal, an alternate to depth first, is an algorithm that searches each level, left to right.

Insertion in level order

Algorithm Steps

  1. Add root node to a queue
  2. Check node in the queue if they have a left child
  3. If not add the new node to the tree in that spot
  4. If there is a left child check if it has a right child of the node
  5. If not, add the new node to the tree in that spot
  6. Add the children of the node to the queue
  7. Check each node in the queue, they will be in a level order, repeating previous steps

Deletion in level order

Full course
Next Lesson