🧩Discrete Mathematics Unit 9 – Trees and Applications

What Are Trees?

• Trees are hierarchical data structures consisting of nodes connected by edges
• Each tree has a root node serving as the starting point, with child nodes branching out from it
• Nodes without any child nodes are called leaf nodes or terminal nodes
• Trees are acyclic, meaning there are no cycles or loops in the structure
• The edges between nodes represent the relationships or connections between them
• Trees have a natural recursive structure, as each subtree is itself a tree
• The depth of a node is the number of edges from the root to that node, with the root having a depth of 0
• The height of a tree is the maximum depth among all its nodes

Types of Trees

• Binary trees have at most two child nodes for each node, referred to as the left child and right child
  • Full binary trees have either zero or two children for every node
  • Complete binary trees have all levels filled except possibly the last, which is filled from left to right
  • Perfect binary trees have all levels completely filled
• N-ary trees allow each node to have up to N children, where N is a fixed constant
• Balanced trees maintain a height of O(log n), ensuring efficient operations (AVL trees, Red-Black trees)
• Unbalanced trees have no height restrictions and can become skewed, leading to inefficient operations
• Trie (prefix tree) is a tree-like data structure used for efficient string searching and prefix matching
• Heap is a specialized tree structure that satisfies the heap property (min-heap or max-heap)
• B-trees are self-balancing trees designed for efficient disk storage and retrieval

Tree Terminology

• Node: A fundamental unit of a tree that contains data and references to its child nodes
• Edge: A connection between two nodes in a tree, representing a parent-child relationship
• Root: The topmost node in a tree, which has no parent and serves as the starting point
• Parent: A node that has one or more child nodes directly connected to it
• Child: A node directly connected to and below its parent node
• Sibling: Nodes that share the same parent are called siblings
• Leaf (terminal node): A node without any child nodes
• Internal node: A node that has at least one child node
• Subtree: A portion of a tree consisting of a node and all its descendants

Tree Traversal Methods

• Preorder traversal: Visit the root, then recursively traverse the left subtree, followed by the right subtree
  • Useful for creating a copy of the tree or exploring paths from the root to leaves
• Inorder traversal (for binary trees): Recursively traverse the left subtree, visit the root, then traverse the right subtree
  • Yields nodes in non-decreasing order for a binary search tree
• Postorder traversal: Recursively traverse the left subtree, then the right subtree, and finally visit the root
  • Useful for deleting nodes or computing expressions in a parse tree
• Level-order traversal (Breadth-First Search): Visit nodes level by level, from left to right
  • Implemented using a queue and useful for finding the shortest path or level-wise processing
• Depth-First Search (DFS): Explore as far as possible along each branch before backtracking
  • Implemented using a stack (implicit in recursion) and useful for path-finding or topological sorting

Binary Trees and Their Properties

• A binary tree is a tree structure where each node has at most two children (left and right)
• The maximum number of nodes at level $i$ is $2^i$ (root is at level 0)
• The maximum number of nodes in a binary tree of height $h$ is $2^{h+1} - 1$
• For a non-empty binary tree, the number of leaf nodes is always one more than the number of internal nodes with two children
• The height of a complete binary tree with $n$ nodes is $\lfloor \log_2(n) \rfloor$
• In a full binary tree, the number of leaf nodes is $\frac{n+1}{2}$, where $n$ is the total number of nodes
• A binary search tree (BST) maintains the property that for each node, all values in its left subtree are smaller, and all values in its right subtree are larger

Tree Applications in Computer Science

• Hierarchical data representation (file systems, XML/HTML documents)
• Expression parsing and evaluation (arithmetic expressions, Boolean expressions)
• Syntax trees in compilers for code analysis and optimization
• Huffman coding trees for data compression
• Balanced search trees (AVL, Red-Black) for efficient searching and sorting
• Heap data structure for priority queues and heap sort algorithm
• Trie for efficient string searching and prefix matching (autocomplete, IP routing tables)
• Spanning trees in network algorithms (Kruskal's, Prim's) for minimum cost connectivity
• Game trees and decision trees in artificial intelligence and game theory

Implementing Trees in Code

• Nodes can be represented using a class or struct with data and child node references
• Recursive algorithms are commonly used to process and manipulate tree structures
• Iterative approaches with explicit stacks or queues can also be used for tree traversals
• Pointer-based implementations are memory-efficient but may have overhead for memory management
• Array-based implementations (e.g., heaps) provide cache-friendly memory layout but may have fixed size constraints
• Balancing algorithms (AVL rotations, Red-Black tree coloring) maintain height balance in self-balancing trees
• Trie implementation uses an array of child node pointers at each node, indexed by character values
• Tree visualization libraries (e.g., D3.js, Graphviz) can be used to display and interact with tree structures

Problem-Solving with Trees

• Recursion is a powerful technique for solving tree-related problems by breaking them down into smaller subproblems
  • Base case: Handle the simplest case directly (e.g., empty tree or leaf node)
  • Recursive case: Solve the problem recursively for subtrees and combine the results
• Induction is often used to prove the correctness of tree algorithms by showing they hold for the base case and the inductive step
• Divide-and-conquer approach divides the problem into smaller subproblems, solves them independently, and combines the results (e.g., merge sort on a BST)
• Dynamic programming can be applied to tree problems with overlapping subproblems (e.g., maximum path sum in a binary tree)
• Greedy algorithms make locally optimal choices at each step (e.g., Huffman coding, Prim's algorithm)
• Backtracking explores all possible solutions by incrementally building candidates and abandoning a candidate as soon as it fails to satisfy the criteria (e.g., generating all binary trees with a given number of nodes)