Abdu's Garden

Trees - The CompSci kind

4 min read

Intro

A common AbstractDataType representing connected, acyclic graphs. Cyclic trees are called Graphs. Remember All trees are graphs, but not all graphs are trees… Often although not necessarily, Trees have a root node, and end nodes known as leaves. Each node in the tree can be connected to one or more children but only one parent, except the root which has no parent.

Representing data in a tree can speed up your algorithms in many natural problems. Two common ways to represent graphs:

  1. Adjacency matrix
    1. matrix
    2. Cell i, j represents an edge from vertex i to j
  2. Adjacency lists:
    1. linked lists – one for each vertex, showing all the neighbors of that vertex

There are many types of Trees we’ve covered many in our Comp3760 Algorithms course at BCIT.

Representing Trees

There are a few different ways of doing so. Some involve OOP and others use fundamental data structures that can be found in most programming languages such as dictionaries and lists.

Node Class (OOP)

This is the typical representation you’ll encounter while studying and practicing. Goes something like this:

# Python class for a typical 'Node' object
class Node(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = No

Array of Arrays

Another way is using a 2-dimensional array. Since each node has one parent, that’d be the outer array. In this representation the structure is as follows:

  • The value of a node is the first element in the array.
  • The left subtree is the second element, which can be another array.
  • the right subtree is the third element and can also be another array. For example:
tree = [
    'a',  #root
    [
        'b',  # left subtree
        ['d' [], []],
        ['e' [], []]
    ],
    [
        'c',  # right subtree
        ['f' [], []],
        []
    ]
]

// I hate this

Accessing

Since it’s an array (or Python list in this example) we can access elements using regular indexing. For example root = tree[0] and the left subtree of the root’s left subtree would be tree[1][1].

Tables/Maps

A table illustrates the nested nature of a tree much better than an array. In this representation, each node has 3 keys, val, left, and right. Obviously, the left and right keys are in turn representing another table with the same keys… This ends up looking like a nested object (it kinda is) but thanks to Map and Table implementations.

my_tree = {
    'val': 'A',
    'left': {
        'val': 'B',
        'left': {'val': 'D'},
        'right': {'val': 'E'}
    },
    'right': {
        'val': 'C',
        'right': {'val': 'F'}
    }
}

Binary Trees

The most infamous type of trees in computer science. A BinaryTree is a tree that has left and right children. In some Binary Trees, a node has a value, and the left child’s value is less than the parent’s and the right’s is greater. These are known as BinarySearchTree or BST.

// In all Binary Trees, the data must be ordered!

Terminology

  • Complete Binary Tree: one in which every level except the last is filled, and all nodes of the last level are to the far left as possible.
  • Balanced Binary Tree: one with a structure in which the height of the left and right sub-trees per node differ by 0 or 1.

Traversal

in-order

//In-order implementation
void inorderTraversal(struct Node* node) {
		if (node == NULL) {
		return;
}
 
 
inorderTraversal(node->left);
printf("%d ", node->data);
inorderTraversal(node->right);
}

Pre-order

void preorderTraversal(struct Node* node) {
		if (node == NULL) {
		return;
}
 
printf("%d ", node->data);
preorderTraversal(node->left);
preorderTraversal(node->right);
}

Post-order

void postorderTraversal(struct Node* node) {
		if (node == NULL) {
		return;
}
 
postorderTraversal(node->left);
postorderTraversal(node->right);
printf("%d ", node->data);
}

Keep in Mind

In-Order traversal of a Binary Tree is insufficient to uniquely serialize a tree. Pre-Order or Post-Order traversal is also required for this.

Binary Search in a Binary Tree

Search for a value recursively in a BinarySearchTree . This algorithm doesn’t work for arrays but concept’s similar. For Arrays checkout Binary Search.

struct node* search(struct node* root, int key) {
	// Base case: the key is not present in the tree or the tree is empty
	if (root == NULL || root->key == key)
			return root;
// If the key is greater than the root's key, it lies in the right subtree
	if (root->key < key)
		return search(root->right, key);
	// If the key is smaller than the root's key, it lies in the left subtree
	return search(root->left, key);
}

Time complexity

OperationBig-O
AccessO(log(n))
SearchO(log(n))
InsertO(log(n))
RemoveO(log(n))
Space complexity of traversing balanced trees is O(h) where h is the height of the tree, while traversing very skewed trees (which is essentially a linked list) will be O(n).

Resources

Graph View

Backlinks