Data structure - Binary Tree

A Binary tree (not to be confused with Binary Search Tree, BST) is a data structure that consists of the following properties:

  1. Only one root node
  2. nodes in a Binary tree are unordered.
  3. two or less branches child nodes.

The connection between nodes are called Edges. The end nodes that do not have children nodes are known as leaf nodes. The depth of a node describes the number of edges a node is from the root and the height of a node is the number of edges from the leaf.

There are many types of tree like data-structures that use a Binary tree data structure, including heap and BST. The type of binary tree is determined by the properties a tree data structure exhibits. For example a Binary tree can be a BST if the Binary tree has BST properties. These properties affect the algorithm’s time complexities for search, insert and delete operations.

3 types of tree data structures,  Binary tree, heap and BST

Implementation

Two common ways to implement a tree data structure includes:

  • Objects/Pointers - Object to represent nodes i a tree and pointers describing the relations between nodes.
  • Arrays - Unsorted/Sorted Array

1. Object/Pointers

Data structures suh as Binary Search Trees are build from objects and pointers instead of arrays. One of the benefit of using objects and pointers is that objects are not staggered in memory. Data structures consisting of objects and pointers do not need to rearrange its member nodes/elements after insertion or deletion since insertion and deletions only involves changing pointer references. (O(1) time complexity operation.)

Searching through Object and Pointers can involve visiting every node in the data structure (e.g.: linked list). However this limitation can be overcome by using data structures for example a Binary Search Tree (BST). BST is an example where the data structure ensures that elements are arranged in a way that allows binary search through its nodes.

Operation Linked list BST
searching O(n) time complexity O(log(2)n)
insert O(1) O(log(2)n)
delete O(1) O(log(2)n)

An example of a node represented by a class.

1
2
3
4
5
6
class Node {
const Parent : Node;
const Left : Node;
const Right : Node;
const value : number; // data value (could be a id etc...)
}

See Binary Search Tree or Linked List for more details.


2. Array

When representing a tree data structure in an array, no pointers are needed. See article Data structure - Heap for an example of an array representing a Heap data structure.

Operation Unsorted Array Sorted Array
searching O(n) time complexity O(log(2)n) time complexity
insert O(n) O(n)
delete O(n) O(n)

Arrays are bad for insert or delete operations because both inserting and deleting an array requires the array elements to be rearranged. For insert operations, elements need to be shifted to make space for the inserted element. Delete operations, elements in an array need to be shifted to “fill” gap created by the element removed from array.

Binary search is an operations used to find an element in an ordered array. Binary search’s efficiency comes from being able to “eliminate” the data set by half for each iteration. Below diagram can help illustrate this…

Example of Binary Search, T(n) is the total work.

Binary Search - Time complexity

For n items in the array, each iteration is n/2. Therefore for i iterations total number of n elements left to be searched:

n/2(i1)\Large n/2^{(i-1)}

Note that it is 2(i1)2^{(i-1)} and not just 2i2^i, because the last iteration will result in either found/not found. The worst case Time complexity would be a total of i1i-1 iterations (max iterations). This is the same as having searched through 2(i1)2^{(i-1)} elements of the array:

n=2(i1)\large n = 2^{(i-1)}

Which is the same as …

log2(n)=i1\large log_2 (n) = i-1

where (i-1) is the worst case time complexity. The below image illustrates the iterations:

Time complexity Analysis of T(i) showing O(log(2)n).

Comparing Binary Tree, Heap and BST

Description Binary Tree Heap (array) Binary Search Tree (array) *
Searching O(n) O(log(2)n) O(log(2)n)
Insertion O(n) O(n) O(log(2)n)
Deletion O(n) O(log(2)n) O(log(2)n)
Sorting NA O(nlog(2)n) NA
Finding Min/Max NA O(1) O(log(2)n)

*1 Note for BST, worst case for unbalanced tree can be O(n)