Skip to content
Permalink
Fetching contributors…
Cannot retrieve contributors at this time
111 lines (81 sloc) 5.37 KB

Tree

A tree is a non-linear data structure where a node can have zero or more connections. The topmost node in a tree is called root. The linked nodes to the root are called children or descendants.

image
Figure 1. Tree Data Structure: root node and descendants.

As you can see in the picture above, this data structure resembles an inverted tree hence the name. It starts with a root node and branch off with its descendants, and finally leaves.

Implementing a Tree

Implementing a tree is not too hard. It’s similar to a part02-linear-data-structures.asc. The main difference is that instead of having a next and previous links, we have an infinite number of linked nodes (children/descendants).

Tree’s node constructor
link:../../../src/data-structures/trees/tree-node.js[]

Simple! Right? But there are some constraints that you have to keep at all times.

Tree data structures constraints
  1. Loops: You have to be careful not to make a circular loop. Otherwise, this wouldn’t be a tree anymore but a graph data structure! E.g., Node A has B as a child, then Node B list Node A as its descendant forming a loop. ‍️

  2. Parents: A node with more than two parents. Again, if that happens is no longer a tree but a part03-graph-data-structures.asc.

  3. Root: a tree must have only one root. Two non-connected parts are not a tree. part03-graph-data-structures.asc can have non-connected portions and doesn’t have root.

Basic concepts

Here’s a summary of the three basic concepts:
  • The topmost node is called root.

  • A node’s immediate linked nodes are called children.

  • A leaf or terminal node is a node without any descendant or children.

  • A node immediate ancestor is called parent. Yep, and like a family tree, a node can have uncles and siblings, and grandparents.

  • Internal nodes are all nodes except for the leaf nodes and the root node.

  • The connection/link between nodes is called edge.

  • The height of a tree is the distance (edge count) from the farthest leaf to the root.

  • The height of a node is obtained by counting the edges between the node and the most distant leaf. For instance, from the image above:

    • Node A has a height of 3.

    • Node G has a height of 1.

    • Node I has a height of 0.

  • The depth of a tree is the distance (edge count) from the root to the farthest leaf.

image
Figure 2. Tree anatomy

Types of Binary Trees

There are different kinds of trees depending on the restrictions. E.g. The trees that have two children or less are called binary tree, while trees with at most three children are called Ternary Tree. Since binary trees are most common we are going to cover them here and others in another chapter.

Binary Tree

The binary restricts the nodes to have at most two children. Trees, in general, can have 3, 4, 23 or more, but not binary trees.

image
Figure 3. Binary tree has at most 2 children while non-binary trees can have more.

Binary trees are one of the most used kinds of tree, and they are used to build other data structures.

Binary Search Tree (BST)

The Binary Search Tree (BST) is a specialization of the binary tree. BST has the same restriction as a binary tree; each node has at most two children. However, there’s another restriction: the values are ordered. It means the left child’s value has to be less or equal than the parent. In turn, the right child’s value has to be bigger than the parent.

BST: left ≤ parent < right

image
Figure 4. BST or ordered binary tree vs. non-BST.
Binary Heap

The heap (max-heap) is a type of binary tree where the children’s values are higher than the parent. Opposed to the BST, the left child doesn’t have to be smaller than the right child.

image
Figure 5. Heap vs BST

The (max) heap has the maximum value in the root, while BST doesn’t.

There are two kinds of heaps: min-heap and max-heap. For a max-heap, the root has the highest value. The heap guarantee that as you move away from the root, the values get smaller. The opposite is true for a min-heap. In a min-heap, the lowest value is at the root, and as you go down the lower to the descendants, they will keep increasing values.

image
Figure 6. Max-heap keeps the highest value at the top while min-heap keep the lowest at the root.
Heap vs. Binary Search Tree

Heap is better at finding max or min values in constant time O(1), while a balanced BST is good a finding any element in O(log n). Heaps are often used to implement priority queues while BST is used when you need every value sorted.

You can’t perform that action at this time.