Trees

Algorithms

---

• Elementary Data Structures
  • Stacks and Queues
  • [Rooted Trees](#rooted\ trees)
• Binary Trees
  • [Full Binary Tree](#full\ binary\ tree)
  • [Complete Binary Tree](#complete\ binary\ tree)
  • [Perfect Binary Tree](#perfect\ binary\ tree)
  • Traversal
    • Pre-order
    • in-order
    • post-order
    • level-order (BFS)
• Binary Search Trees
  • Search()
  • Insert()
  • Print()
  • Max()/Min()
  • Delete()
    • Lazy
    • Actual
  • Contains()
  • Complexity Analysis
• Practice
• Balanced Binary Search Trees
  • AVL Trees
    • Rebalancing
  • Red-Black Trees
    • Recoloring
  • Splay Trees
• B trees

---

Data Structures

Stacks

Last In First Out (LIFO)

• PUSH()
• POP()
• TOP()

1. using arrays

each operation is $O(1)$

#define STACK_CAPACITY 100
 
typedef struct Stack {
	int stack[STACK_CAPACITY];
	int top; // index of top element
} stack;
 
int isEmpty (stack* s) { 
	if (s.top == 0) 
		return true;
	else 
		return false;
}
 
void push (stack* s, int n) {
	s.top++;
	s.stack[s.top] = n;
}
 
void pop (stack* s) {
	if (isEmpty(s)) 
		exit 1;
	else {
		s.top--;
		return s.stack[s.top + 1]; // return the popped element
	}
}

2. using linked lists

each operation is $O(1)$

#include<stdlib.h>
#include<stdio.h>
 
typedef struct Node {
	int data;
	struct Node* next;
} Node;
 
Node* createNode(int data) {
	Node* new_node = (Node*) malloc(sizeof(Node));
	new_node->data = data;
	new_node->next = NULL;
	return new_node;
}
 
typedef struct Stack {
	Node* head;
} Stack;
 
void initStack(Stack* stack) {
	stack->head = NULL;
}
 
int isEmpty(Stack* stack) {
	return stack->head == NULL;
}
 
void push(Stack* stack, int data) {
	Node* new_node = createNode(data);
	if (!new_node) {
		exit 1; // stack overflow
	}
	new_node->next = stack->head;
	stack->head = new_node;
}
 
void pop(Stack* stack) {
	if (isEmpty(stack)) {
		exit 2; // stack underflow
	}
	else {
		Node* temp = stack->head;
		stack->head = stack->head->next;
		free(temp);
	}
}

Queues

First In First Out (FIFO)

• ENQUEUE()
• DEQUEUE()
• HEAD()
• TAIL()

1. array implementation

#define QUEUE_CAPACITY 100
 
typedef struct Queue {
	int head; // init head = 0
	int tail; // init tail = 0
	int queue[QUEUE_CAPACTIY];
} Queue;
 
void enqueue(Queue* q, int data) {
	q.queue[q.tail] = data;
	q.tail = (q.tail + 1) % QUEUE_CAPACITY;
}
 
int dequeue(Queue* q) {
	int x = q.queue[q.head];
	q.head = (q.head + 1) % QUEUE_CAPACITY;
	return x;
}

2. linked list

typedef struct Node {
	int data;
	struct Node* next;
} Node;
 
Node* createNode (int data) {
	Node* new_node = (Node*) malloc(sizeof(Node));
	new_node->data = data;
	new_node->next = NULL;
	return new_node;
}
 
typedef struct Queue {
	Node* front;
	Node* rear;
} Queue;
 
Queue* initQueue() {
	Queue* q = (Queue*) malloc(sizeof(Queue));
	q->front = q->rear = NULL;
	return q;
}
 
int isEmpty(Queue* q) {
	return q->rear == q->front && q->front == NULL;
}
 
void enqueue(Queue* q, int data) {
	Node* new_node = createNode(data);
	if (isEmpty(q)) {
		q->front = q->rear = new_node;
		return;
	}
	q->rear->next = new_node;
	q->rear = new_node;
}
 
void deqeue(Queue* q) {
	if (isEmpty(q)){
		exit 1; // Queue underflow	
	}
	Node* temp = q->front;
	q->front = q->front->next;
	free(temp);
}

Rooted Trees

Unbounded Branching Implementation

• each node is a linked list with data and two pointers
• first pointer links to the first child, and the second pointer to the next sibling

typedef struct Node {
	int data;
	struct Node* left_child;
	struct Node* right_sibling;
} Node;

---

Binary Trees

each node has at most two children → left_child → right_child

Full Binary Tree

every node has either 0 or two children

The number of leaves in a non-empty full binary tree is one more than the number of internal nodes. You can notice this in the image.

Complete Binary Tree

Every level except possible the last one is completely filled, and all nodes in the last level are as far left as possible.

Memory Aid “Complete” is a wider word than “Full” and you can remember that Complete Trees are typically wider than Full Trees

Perfect Binary Tree

All internal nodes have two children and all leaf nodes have the same depth

Implementation:

typedef struct node {
	int data;
	struct node* left;
	struct node* right;
} node;
 
node* newNode (int data) {
	node* node = (node*) malloc(sizeof((node));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}

Binary Tree Traversal

From a node N:

• (N): process N itself
• (L): recurse on N’s left subtree
• (R): recurse on N’s right subtree

Pre-Order Traversal (NLR)

void printPreorder (node* node) {
	if (node == NULL)
		return;
	// print (N)
	printf("%d ", node->data);
	// recurse on (L)
	printPreorder(node->left);
	//recurse on (R)
	printPreorder(node->right);
}

In-Order Traversal (LNR)

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

Morris Traversal

Recursion and Stack Methods include $O(n)$ space complexity. To avoid this additional space overhead we can modify the original tree and convert it to a Threaded Binary Tree using Morris Traversal

class Solution {
	vector<int> result{};
public:
	vector<int> inorderTraversal(TreeNode* root) {
	TreeNode* curr = root;
	while(curr) {
		if (curr->left == nullptr) {
		result.push_back(curr->val);
		curr = curr->right;
	} else {
		TreeNode* tmp = curr->left;
		while (tmp->right != nullptr) tmp = tmp->right;
		tmp->right = curr;
		curr = curr->left;
		tmp->right->left = nullptr;
		}
	}
	return result;
	}
};

My solution to Leetcode 94

Post-Order Traversal (LRN)

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

Level Order Traversal (BFS)

>> 1
>> 2 3
>> 4 5 0 0 

void BFS(Node* root) {
	if (root == NULL) 
		return;
	enqueue(q, root);
	while(q.front != NULL) {
		Node* curr = dequeue(q);
		printf("%d ", curr->data);
		if (root->left != NULL)
			enqueue(q, root->left);
		if (root->right != NULL)
			enqueue(q, root->right);
	}
}

---

Binary Search Trees

binary tree in which every node contains a value greater than left_child and lesser than right_child

Search()

Node* search(Node* root, int query) {
	if (root == NULL || root->data == query)
		return root;
	if (query < root->data) 
		return search(root->left, query);
	else
		return search(root->right, query);
	return root;
}

Insert()

Node* insert(Node* root, int data) {
	if (root == NULL)
		return createNode(data);
	if (key < root->data)
		root->left = insert(root->left, data);
	else if (data > root->data)
		root->right = insert(root->right, data);
	else 
		printf("%d already present\n", data);
	return root;
}

• running time $O(h)$ h = height
• worst case with n different nodes = $O(n)$

Max()/Min()

go as far left or right as possible

int getMax(Node* root) {
	while (node->right != NULL) {
		root = root->right;
	}
	return root->data;
}
 
int getMin(Node* root) {
	while (root->left != NULL) 
		root = root->left;
	return root->data;	
}

Delete()

Lazy Node Deletion

Don’t actually delete the node. Keep the data and mark the node as ‘disabled’. Upon a later insertion of the same data, the node can be easily re-enabled.

Actual Node Deletion

3 cases

1. leaf node (no child)
2. internal node (one child)
3. internal node (two children)

Case 1: just remove it

Case 2: replace it with it’s child

Case 3: let $D$ be the node to be deleted

• find min() in right subtree and copy its value to $D$
• recursively delete that min() value

Node* delete(Node* root, int data) {
	// key not found
	if (root == NULL)
		return NULL;
	//recur down the tree
	if (data < root->data)
		root->left = delete(root->left, data);
	else if (data > root->data)
		root->right = delete(root->right, data);
	// if data == root->key then root is to be deleted
	else {
		// if leaf node
		if (root->left == NULL && root->right == NULL){
			free(root);
			return NULL;
		}
		// if node with left child only
		else if (root->right == NULL) {
			Node* temp = root->left;
			free(root);
			return temp;
		}
		// if node with right child only
		else if (root->left == NULL) {
			Node* temp = root->right;
			free(root);
			return temp;
		}
		// if both children with min node in the right subtree
		else {
			Node* temp = getMin(root->right);
			root->data = temp->data;
			root->right = delete(root->right, temp->data);
		}
	}
	return root;
}

Complexity Analysis

running time of all operations is $O(d)$ (d = depth), apart from traversal which is necessarily $O(n)$ (n = nodes)

HOWEVER: tree shape depends on the order of insertion, at best if the tree is complete its height is $O(\log n)$ and randomly also it’s around that, but it’s very easy for the trees to become unbalanced to one side

Worst Case running time is $O(n)$ in a completely unbalanced tree

---

Practice

Practice from here

---

Balanced Trees

Trees

• 1962: first self balancing BST

For each node, the heights of left and right subtrees can differ by at most 1

• This difference is called the node’s balance factor

Rebalancing