Trees and Binary Trees Lecture Notes

Overview of Tree Structures

• Linear vs. Non-linear Hierarchies:     * Linear data structures such as lists, arrays, queues, stacks, and linked lists define elements in a sequential order with items preceding and following one another.     * Trees are non-linear structures used when data requires a hierarchical order, defining relationships where some data is "above" and some is "below" other data.

• Applications of Trees:     * Data Science.     * Databases.     * Artificial Intelligence (AI).     * Computer Graphics.     * Operating Systems (OS).

• Performance Benefits: Tree structures are often significantly faster for certain operations compared to linear structures.

Defining the Tree Abstract Model

• Generic Definition: In computer science, a tree is an abstract model representing a hierarchical structure.

• Structural Composition: A tree consists of nodes linked by parent-child relationships.

• Real-World Application Examples:     * Organization Charts: For instance, a company named Computers "R" Us might have top-level categories for Sales, Manufacturing, and R&D. Under Sales, there may be US and International. Under US, categories like Laptops and Desktops reside, while International branches into Europe, Asia, and Canada.     * File Systems: Nested directories and files represent a classic hierarchy.     * Programming Environments.

Tree Terminology and Properties

• Core Components:     * Root: The node at the very top of the hierarchy with no parent (e.g., node A in traditional diagrams). It serves as the primary access point to the entire tree.     * Internal Node: Any node that possesses at least one child (e.g., nodes A, B, C, F).     * External Node (Leaf): A node that has no children (e.g., nodes E, I, J, K, G, H, D).     * Siblings: Nodes that share the same parent.     * Edges: The connections between nodes.

• Relationships and Paths:     * Ancestors of a Node: Includes the parent, grandparent, great-grandparent, and so on, continuing up to the root.     * Descendant of a Node: Includes the child, grandchild, great-grandchild, and so on.     * Subtree: A structure consisting of a specific node and all of its descendants.     * Path: The sequence of nodes encountered when following edges from the root to a specific destination node.

• Measurements:     * Depth of a Node: The number of ancestors the node has.     * Height of a Tree: Defined as the maximum depth of any node within the tree (e.g., a tree with a maximum depth of 3 has a height of 3).     * Recursive Nature: Trees are inherently recursive. Every node can be viewed as the root of its own subtree, consisting of a set of nodes and edges.     * Ordered Trees: A tree is considered "ordered" if there is a specific, defined sequence for the children of every node.

The Binary Tree Abstract Data Type (ADT)

• General Characteristics:     * The Binary Tree is one of the most common tree types in computer science.     * Constraint: Each node can have a maximum of 2 children.     * Children Labels: Left child and Right child.

• Organization by Levels:     * The root is defined as being at Level 0.

• Tree Metrics Comparison (Specific Examples):     * Example A: Depth of node H is $3$; Height of tree is $3$; Width (most nodes) is $4$ (at Level 2); Total size (nodes) is $9$.     * Example B: Depth of node H is $4$; Height of tree is $5$; Width is $3$ (at Level 2).     * Example C: Depth of node H is $7$; Height of tree is $7$; Width is $1$.

• Size vs. Height:     * A tree with 6 nodes has a maximum potential height of $6$ (where there is exactly 1 node per level).     * Minimum Height: To calculate the minimum height, one must maximize the number of nodes at each level.     * Formula: The minimum height of a tree with size $n$ is given by $\lceil ext{log}_2 n ceil$.

Binary Tree Structural Classifications

• Full Binary Tree: A structure where every internal node contains either zero or exactly two children.

• Perfect Binary Tree: A structure where all possible node positions are filled across every level. All leaf nodes are located on the same final level.

Python Implementation of Binary Trees

• The Private Node Class: Defined as _BinTreeNode, which stores an element and links to two children. python class _BinTreeNode: def __init__(self, element): self._element = element self._right = None self._left = None     

• The Public BinaryTree Class: Consists of a constructor that initializes the root with a given value. ```python class BinaryTree: def init(self, root): self._root = _BinTreeNode(root)

  myTree = BinaryTree(1)     ```

Systematic Tree Traversal Algorithms

• Objective: To visit every node in a tree systematically. Unlike linear structures with single pointers, trees have no single path.

• Time Complexity: The running time for traversing a tree is $O(n)$, where $n$ is the total number of nodes.

• Primary Categories:     1. Breadth First Traversal (Width-first).     2. Depth First Traversal, which includes Pre-order, In-order, and Post-order approaches.

Depth First Traversal Details

• Pre-order Traversal:     * Order: The current node is visited before its descendants.     * Mechanism: Start at the root, follow the left node first, then the right. It uses recursion with a base case encountered at a NULL child.     * Application: Printing structured documents.     * Python Logic: python def preOrder(self, start): if start: print(start._element) self.preOrder(start._left) self.preOrder(start._right)         

• In-order Traversal:     * Order: Nodes are read from left to right.     * Mechanism: Traverse the left subtree, visit the node itself, then traverse the right subtree.     * Execution Strategy: Start at the root, go as far left as possible, print that node, move up to print the parent, then move right and repeat the "far-left" search.     * Python Logic: python def inOrder(self, start): if start: self.inOrder(start._left) print(start._element) self.inOrder(start._right)         

• Post-order Traversal:     * Order: A node is visited only after all its descendants have been visited.     * Mechanism: Process the children first, then the root. Start at the root, descend as far left as possible, then far right, and finally the local root.     * Application Scenario: File system sizes where directories are calculated after their contents (e.g., DDR.java ($10 ext{K}$), Stocks.java ($25 ext{K}$), Robot.java ($20 ext{K}$)).     * Python Logic: python def postOrder(self, start): if start: self.postOrder(start._left) self.postOrder(start._right) print(start._element)         

Breadth First Traversal

• Mechanism: Nodes are visited level by level (Level 0, then Level 1, etc.) from left to right.

• Recursive Limitation: Recursion cannot be used for Breadth First because recursion naturally leads deeper into the tree (depth-wise).

• Implementation Requirement: A Queue is required to store child nodes in order before processing specific levels.

• Algorithm Step-by-Step:     1. Initialize Queue q with the root.     2. While q is not empty, dequeue the oldest element.     3. Print that element.     4. If the left child is not Null, enqueue it.     5. If the right child is not Null, enqueue it.

• Python Logic: python def breadthFirst(self): q = ArrayQueue() q.enqueue(self._root) while not q.is_empty(): node = q.dequeue() print(node._element) if node._left is not None: q.enqueue(node._left) if node._right is not None: q.enqueue(node._right)     

Calculations and Specialized Trees

• Calculating Size of a Tree:     * Determining the size is done recursively similarly to a traversal.     * Base Case: If the node is None, return $0$.     * Recursive Step: Return $1 + \text{printSize}(\text{left node}) + \text{printSize}(\text{right node})$.     * Python Implementation: python def printSize(self, start): if start: return (1 + self.printSize(start._left) + self.printSize(start._right)) else: return 0         

• Arithmetic Expression Trees:     * Arithmetic expressions can be converted into Binary Trees.     * Benefit: The tree structure inherently handles order of operations, so no parentheses are required within the data structure itself.     * Node Storage:         * Internal nodes store operators (e.g., $,$, $,$).         * External nodes (leaves) store operands (variables or numbers).     * Example Expression: $(2 \times (a - 1) + (3 \times b))$     * Traversal for Evaluation: An in-order traversal yields the familiar infix representation.     * Parenthesis Printing Logic:         * Print an opening parenthesis "(" before traversing a left subtree.         * Print node element (operand or operator).         * Print a closing parenthesis ")" after traversing a right subtree.     * Algorithm Template: Algorithm printExpression(v) if v has a left child: print("(") inOrder(left(v)) print(v.element()) if v has a right child: inOrder(right(v)) print(")")