Trees

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. $|V|x|V|$ matrix
   2. Cell i, j represents an edge from vertex i to j
2. Adjacency lists:
   1. $|V|$ 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.

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.

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. This algorithm is for a Binary Trees only, 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

Operation	Big-O
Access	O(log(n))
Search	O(log(n))
Insert	O(log(n))
Remove	O(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

• Tech Interview Handbook-Trees