Trees and Binary Trees Overview

Trees

• Trees are hierarchical data structures that store information in a hierarchy style
• A tree is a non-linear data structure unlike arrays, linked lists, stack and queue
• Data is stored in nodes, linked together by edges
• The topmost node is the root node
• Each node contains data and links to other nodes, known as children
• Trees are recursive as the root node has links to the roots of its subtrees
• The number of edges in a tree is n-1, where n is the number of nodes

Binary Tree

• A binary tree is a special tree where each node can have at most two children
• Each node can have zero, one, or two children

Properties of Binary Tree

• At each level i, the maximum number of nodes is 2^i
• The height of the tree is the longest path from the root to a leaf node
• The maximum number of nodes in a tree with height h is 2^(h+1)-1
• The minimum number of nodes in a tree with height h is h+1
• If there are n nodes in a binary tree, the minimum height can be calculated as log2(n+1) -1

Types of Binary Tree

• Full/Proper/Strict Binary Tree: Each node has 0 or 2 children. The number of leaf nodes is equal to the number of internal nodes plus 1.
• Complete Binary Tree: All nodes are completely filled except for the last level, where nodes must be filled as left as possible.
• Perfect Binary Tree: All internal nodes have 2 children and all leaf nodes are at the same level.
• Degenerate Binary Tree: All internal nodes have only one child.
• Balanced Binary Tree: The difference in height between the left and right subtrees is at most 1. AVL and Red-Black Trees are balanced binary trees.

Binary Tree Traversal

• Tree traversal involves visiting each node in a specific order.
• Inorder Traversal: Left Root Right. Used for searching in BST.
• Preorder Traversal: Root Left Right. Used for creating a copy of a tree.
• Postorder Traversal: Left Right Root. Used for deleting a tree.

Binary Search Tree (BST)

• A binary search tree is a binary tree that follows the property that the value of each node is greater than or equal to all values in its left subtree and less than or equal to all values in its right subtree.
• Search in BST: Use a recursive approach. Start at the root node, if the item to be searched is equal to the root node, then return the root node, else if the item is less than the root, search recursively in the left subtree, otherwise search recursively in the right subtree.
• Insertion in BST: Add a new node, maintaining the BST properties. Allocate memory for a new node, set its data, let its left and right pointers point to NULL. If the item is less than the root, insert recursively in the left subtree, otherwise in the right subtree.
• Deletion in BST: Delete a node while maintaining BST properties.
  • Leaf Node: Replace the node with NULL and free the allocated space.
  • Node with one child: Replace the node with its child and delete the child.
  • Node with two children: Replace the node with its inorder successor (the smallest node in the right subtree).

Huffman Encoding

• A greedy algorithm that creates an optimal prefix code, known as Huffman Code
• Builds a tree using a set of characters and their frequencies, starting from the leaves and merging nodes in a bottom-up manner
• Aims to minimize the average code length for a message

AVL Trees

• AVL Trees are height-balanced binary search trees.
• Each node has a balance factor, calculated by subtracting the height of its right subtree from the height of its left subtree.
• Balance factor is between -1 and 1, allowing the tree to be balanced.
• Importance: AVL trees prevent the binary search tree from becoming skewed.

LR Rotations

• Used to balance an AVL tree when an insertion causes an imbalance.
• Performed when a node is inserted into the right subtree of the left subtree, leading to an unbalanced node.
• Involves performing a left rotation followed by a right rotation.

This quiz covers the fundamental concepts of trees and binary trees in data structures. It discusses the hierarchy of tree nodes, properties of binary trees, and their characteristics, including maximum and minimum nodes and heights. Test your understanding of how trees function as non-linear data structures.