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.

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.

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.

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…

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:

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

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

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

Which is the same as …

$\large log_2 (n) = i-1$

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

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)