LEARNING OUTCOME 7

Tree Data Structure

A tree is a non-linear data structure that consists of nodes connected by edges. It resembles an inverted tree, with a root node at the top and branches extending downwards. Each node can have zero or more child nodes.

Properties of a Tree Data Structure:

• Root Node: The topmost node of the tree.
• Parent Node: A node that has one or more child nodes.
• Child Node: A node that has a parent node.
• Leaf Node: A node with no children.
• Degree of a Node: The number of children of a node.
• Level of a Node: The distance of a node from the root node.
• Height of a Tree: The maximum level of any node in the tree.
• Depth of a Node: The number of edges from the root node to the node.

Different Types of Trees

Here are some common types of trees in computer science:

General Trees

• General Tree: A tree where each node can have any number of children.

Binary Trees

• Binary Tree: A tree where each node has at most two children, referred to as the left child and the right child.
• Binary Search Tree (BST): A binary tree where the left subtree contains nodes with keys less than the root node's key, and the right subtree contains nodes with keys greater than the root node's key.
• Complete Binary Tree: A binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.
• Full Binary Tree: A binary tree in which every node has either 0 or 2 children.
• Perfect Binary Tree: A binary tree in which all internal nodes have two children, and all leaves are at the same level.

Special Trees

• AVL Tree: A self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one.
• Red-Black Tree: A self-balancing binary search tree that uses color coding (red or black) to maintain balance.
• B-Tree: A self-balancing tree that maintains sorted data and allows efficient insertions, deletions, and searches.
• Heap: A specialized tree-based data structure that satisfies the heap property: the parent node is always greater than or equal to (in a max heap) or less than or equal to (in a min heap) its children.
• Trie: A tree-like data structure used to store strings. Each node represents a character, and the path from the root to a leaf represents a word.

Binary Tree Operations

A binary tree is a fundamental data structure in computer science. It consists of nodes, where each node has at most two children: a left child and a right child.

What is a Binary Tree?

A binary tree is a hierarchical data structure where each node has at most two children: a left child and a right child. The topmost node is called the root. Nodes without children are called leaves.

Key Concepts

• Node: A basic unit of a tree, containing data and pointers to its left and right children.
• Root: The top-most node of the tree.
• Leaf: A node with no children.
• Parent: A node that has one or more children.
• Child: A node connected to another node (its parent).
• Subtree: A portion of the tree that is itself a tree, rooted at a particular node.

Binary Tree Operations

Here's a detailed explanation of common binary tree operations:

1. Insertion

The goal is to add a new node containing a specific value while maintaining the binary tree's structure (often a Binary Search Tree, where left child <= parent < right child).

1. Find the Insertion Point:
   • Start at the root.
   • If the new value is less than the current node's value, move to the left child.
   • If the new value is greater than or equal to the current node's value, move to the right child.
   • Repeat until you reach a nullptr (an empty spot). This is where the new node will be inserted.
2. Create the New Node:
   • Allocate memory for a new node.
   • Set the new node's data to the value being inserted.
   • Initialize the new node's left and right pointers to nullptr.
3. Link the New Node:
   • If the new value is less than the parent's value, make the new node the parent's left child.
   • Otherwise, make the new node the parent's right child.

2. Deletion

Deleting a node involves several cases to maintain the tree's structure:

1. Case 1: Node to be deleted is a leaf (no children):
   • Simply remove the node by setting the parent's corresponding child pointer (left or right) to nullptr.
2. Case 2: Node to be deleted has one child:
   • Replace the node with its child. Update the parent's pointer to point to the node's child.
3. Case 3: Node to be deleted has two children:
   • Find the inorder successor (smallest node in the right subtree) or the inorder predecessor (largest node in the left subtree).
   • Copy the value of the inorder successor/predecessor to the node being deleted.
   • Delete the inorder successor/predecessor (which will now have at most one child, so it falls into Case 1 or 2).

3. Searching

Searching for a specific value in a binary search tree is efficient:

1. Start at the root.
2. Compare the target value with the current node's value.
3. If they are equal, the value is found.
4. If the target value is less than the current node's value, move to the left child.
5. If the target value is greater than the current node's value, move to the right child.
6. Repeat until the value is found or you reach a nullptr (value not in the tree).

4. Tree Traversals

Tree traversals are systematic ways to visit every node in the tree exactly once.

1. a. Inorder Traversal (Left, Root, Right): Often used for binary search trees because it visits nodes in sorted order.
   • Traverse the left subtree (recursively).
   • Visit the current node (process its data).
   • Traverse the right subtree (recursively).
2. b. Preorder Traversal (Root, Left, Right):
   • Visit the current node (process its data).
   • Traverse the left subtree (recursively).
   • Traverse the right subtree (recursively).
3. c. Postorder Traversal (Left, Right, Root):
   • Traverse the left subtree (recursively).
   • Traverse the right subtree (recursively).
   • Visit the current node (process its data).

Example (Conceptual C++ Code Snippet - Insertion)

		
		struct Node {
			int data;
			Node* left;
			Node* right;
		};
		
		Node* insert(Node* root, int value) {
			if (root == nullptr) {
				Node* newNode = new Node;
				newNode->data = value;
				newNode->left = newNode->right = nullptr;
				return newNode;
			}
		
			if (value < root->data) {
				root->left = insert(root->left, value);
			} else {
				root->right = insert(root->right, value);
			}
			return root;
		}
		
		

					
		#include <iostream>
		#include <limits>
		
		struct Node {
			int data;
			Node* left;
			Node* right;
		
			Node(int val) : data(val), left(nullptr), right(nullptr) {}
		};
		
		class BinaryTree {
		private:
			Node* root;
		
			Node* findInorderSuccessor(Node* node) {
				while (node->left != nullptr) {
					node = node->left;
				}
				return node;
			}
		
			Node* deleteNodeRecursive(Node* root, int key) {
				if (root == nullptr) return root;
		
				if (key < root->data)
					root->left = deleteNodeRecursive(root->left, key);
				else if (key > root->data)
					root->right = deleteNodeRecursive(root->right, key);
				else {
					if (root->left == nullptr) {
						Node* temp = root->right;
						delete root;
						return temp;
					} else if (root->right == nullptr) {
						Node* temp = root->left;
						delete root;
						return temp;
					}
		
					Node* temp = findInorderSuccessor(root->right);
					root->data = temp->data;
					root->right = deleteNodeRecursive(root->right, temp->data);
				}
				return root;
			}
		
		public:
			BinaryTree() : root(nullptr) {}
		
			Node* insert(Node* root, int value) {
				if (root == nullptr) {
					return new Node(value);
				}
		
				if (value < root->data) {
					root->left = insert(root->left, value);
				} else {
					root->right = insert(root->right, value);
				}
				return root;
			}
		
			void insert(int value) {
				root = insert(root, value);
			}
		
			void deleteNode(int key) {
				root = deleteNodeRecursive(root, key);
			}
		
			bool search(Node* root, int key) {
				if (root == nullptr) return false;
				if (root->data == key) return true;
		
				if (key < root->data) {
					return search(root->left, key);
				} else {
					return search(root->right, key);
				}
			}
		
			bool search(int key) {
				return search(root, key);
			}
		
			void inorder(Node* root) {
				if (root != nullptr) {
					inorder(root->left);
					std::cout << root->data << " ";
					inorder(root->right);
				}
			}
		
			void inorder() {
				inorder(root);
				std::cout << std::endl;
			}
		
			void preorder(Node* root) {
				if (root != nullptr) {
					std::cout << root->data << " ";
					preorder(root->left);
					preorder(root->right);
				}
			}
		
			void preorder() {
				preorder(root);
				std::cout << std::endl;
			}
		
			void postorder(Node* root) {
				if (root != nullptr) {
					postorder(root->left);
					postorder(root->right);
					std::cout << root->data << " ";
				}
			}
		
			void postorder() {
				postorder(root);
				std::cout << std::endl;
			}
		};
		
		int main() {
			BinaryTree tree;
		
			tree.insert(50);
			tree.insert(30);
			tree.insert(20);
			tree.insert(40);
			tree.insert(70);
			tree.insert(60);
			tree.insert(80);
		
			std::cout << "Inorder traversal: ";
			tree.inorder();
			std::cout << "Preorder traversal: ";
			tree.preorder();
			std::cout << "Postorder traversal: ";
			tree.postorder();
		
			std::cout << "Search for 40: " << (tree.search(40) ? "Found" : "Not Found") << std::endl;
			std::cout << "Search for 99: " << (tree.search(99) ? "Found" : "Not Found") << std::endl;
		
			tree.deleteNode(30);
			std::cout << "Inorder traversal after deleting 30: ";
			tree.inorder();
		
			return 0;
		}
					
				

Binary Search Tree (BST)

Definition

A Binary Search Tree (BST) is a specific type of binary tree where:

• Left Subtree Property: All nodes in the left subtree of a node have keys less than the node's key.
• Right Subtree Property: All nodes in the right subtree of a node have keys greater than the node's key.

This property allows for efficient searching, insertion, and deletion of elements.

Applications of Binary Search Trees

• Efficient Searching: BSTs allow for logarithmic time search operations.
• Sorting: In-order traversal of a BST yields a sorted list of elements.
• Symbol Tables: Used to store key-value pairs efficiently.
• Priority Queues: Can be implemented using BSTs to efficiently prioritize elements.
• Range Queries: Finding elements within a specific range can be optimized using BSTs.
• Set and Map Implementations: Many set and map implementations in standard libraries are based on BSTs.
• Huffman Coding: Used to compress data by assigning shorter codes to more frequent characters.