Data Structures: Trees and Binary Search Trees Complete Study Guide

Introduction to Trees

• Definition of Data Structures:     * Linear Data Structures: A data structure is considered linear if its elements form a sequence or a linear list. Examples previously studied include arrays, stacks, queues, and linked lists.     * Non-Linear Data Structures: A data structure is non-linear if its elements form a hierarchical classification where data items appear at various levels.

• Trees and Graphs as Non-Linear Structures:     * Both are widely used to represent hierarchical relationships between individual data elements.     * Relationship: Graphs are general structures. Trees represent a special case of graphs with specific restrictions. In a graph, there are no restrictions on the number of links entering or leaving a node, and cycles may be present. Trees lack cycles and have strict link restrictions.

• Recursive Definition of a Tree:     * A tree is a finite set of one or more nodes such that:         1. There is a specially designated node called the root.         2. The remaining nodes are partitioned into $n \ge 0$ disjoint sets $T_{1}, …, T_{n}$, where each of these sets is itself a tree. These sets are called the subtrees of the root.

• Hierarchical Structure:     * The root node is at the top of the hierarchy.     * Each node can have at most one link coming into it (one parent).     * The node where a link originates is the parent node.     * The root node has no parent.     * Links leaving a node point to child nodes; any number of outgoing links are allowed.     * Nodes at the bottom with no children are called leaf nodes.

• Advantages of Trees:     * They reflect structural relationships within the data.     * They are used to effectively represent hierarchies.     * They provide efficient insertion and searching capabilities.     * They are flexible, allowing subtrees to be moved with minimum effort.

Tree Terminology

• Node: Every individual element in a tree. It stores the actual data and links to the next elements in the hierarchy.

• Root: The first node in a tree data structure. Every tree must have exactly one root node; multiple roots are not allowed. It is the origin of the tree.

• Edge: The connecting link between any two nodes. In a tree with $N$ nodes, there are a maximum of $N - 1$ edges.

• Parent: The predecessor of any node. It is a node that has a branch originating from it to another node (has child/children).

• Child: The descendant of any node. It is a node that has a link from its parent. All nodes except the root are child nodes.

• Siblings: Nodes that belong to the same parent.

• Leaf (Terminal/External Node): A node which does not have a child, or a node with a degree of zero.

• Internal Node (Non-Terminal Node): A node that has at least one child. In trees with more than one node, the root is also an internal node.

• Degree:     * Degree of a Node: The total number of children or subtrees of that node.     * Degree of a Tree: The highest degree of any node among all nodes in the tree.

• Level: The root is at Level 0. Its children are at Level 1, their children at Level 2, and so on. Each step from top to bottom is a level. Note: Some authors start the root level at 1.

• Height:     * Height of a Node: The total number of edges from a leaf node to that particular node in the longest path.     * Height of a Tree: The height of the root node. The height of all leaf nodes is defined as $0$. A null tree has a height of $-1$.

• Depth:     * Depth of a Node: The total number of edges from the root node to that particular node.     * Depth of a Tree: The total number of edges from the root to a leaf node in the longest path (the highest depth of any leaf node). The depth of the root node is $0$.

• Path: A sequence of nodes and edges from one node to another. The length of a path is the total number of nodes in that path (e.g., path $A - B - E - J$ has length 4).

• Sub Tree: Each child from a node forms a subtree recursively.

Tree Representations

• List Representation:     * Uses two types of nodes: one for data and another for references.     * Starts with a data node (root), linked to an internal node via a reference node, which directs to other nodes.

• Left Child - Right Sibling (LCRS) Representation:     * Uses a node structure with three fields:         1. Data Field: Stores the actual value.         2. Left Child Reference Field: Stores the address of the left child; if none exists, it is $NULL$.         3. Right Sibling Reference Field: Stores the address of the right sibling; if none exists, it is $NULL$.

• Representation as a Degree-Two Tree:     * To obtain this, rotate the right-sibling pointers in an LCRS tree clockwise by 45 degrees. The two children are referred to as left and right children.

Binary Trees

• Definition: A binary tree is a special tree where every node can have a maximum of 2 children, known as the left child and the right child. Every node has either 0, 1, or 2 children.

• Strictly Binary Tree (Full/Proper/2-Tree): A binary tree where every node has either exactly two children or zero children. Every internal node must have exactly two children.

• Complete Binary Tree (Perfect Binary Tree): A binary tree where every internal node has exactly two children and all leaf nodes are at the same level. At every level $i$, there must be $2^{i}$ nodes (if using level starting at 0 notation).

• Extended Binary Tree: A binary tree converted into a full binary tree by adding dummy nodes to existing nodes wherever required.

• Abstract Data Type (ADT):     * Definition: A finite set of nodes that is either empty or consists of a root and two disjoint binary trees (left subtree and right subtree).     * Functions:         * Create(): Creates an empty binary tree.         * IsEmpty(bt): Returns TRUE if the tree is empty.         * MakeBT(bt1, item, bt2): Returns a tree with root item, left subtree bt1, and right subtree bt2.         * Lchild(bt): Returns the left subtree.         * Data(bt): Returns the data in the root.         * Rchild(bt): Returns the right subtree.

• Differences between a Tree and a Binary Tree:     * Binary tree subtrees are ordered (left vs right); standard trees are not ordered.     * A binary tree can be empty; a tree (by the definition provided) consists of one or more nodes.

Properties of Binary Trees

• Maximum Nodes:     1. The maximum number of nodes on level $i$ is $2^{i-1}$, for $i \ge 1$.     2. The maximum number of nodes in a binary tree of depth $k$ is $2^{k} - 1$, for $k \ge 1$.     * Proof by Induction (Max nodes on level i):         * Base: For $i = 1$, root is the only node. $2^{1-1} = 2^{0} = 1$.         * Hypothesis: Max nodes on level $i - 1$ is $2^{i-2}$.         * Step: Since max degree is 2, level $i$ has at most $2 \times 2^{i-2} = 2^{i-1}$.

• Relation between Leaf and Degree-2 Nodes:     * For any nonempty binary tree $T$, if $n_{0}$ is the number of leaf nodes and $n_{2}$ is the number of nodes of degree 2, then $n_{0} = n_{2} + 1$.     * Proof: Let $n$ be total nodes and $B$ be total branches. $B+1=n$. Also, $B = n_{1} + 2n_{2}$ (where $n_{1}$ is degree-1 nodes). Thus, $n_{1} + 2n_{2} + 1 = n_{0} + n_{1} + n_{2}$, which simplifies to $n_{2} + 1 = n_{0}$.

• Full vs. Complete:     * A full binary tree of depth $k$ has $2^{k} - 1$ nodes ($k \ge 0$).     * A binary tree with $n$ nodes and depth $k$ is complete if its nodes correspond to the nodes numbered 1 to $n$ in a full binary tree.

Binary Tree Representation

• Array (Sequential) Representation:     * Uses a 1-D array. For a tree of depth $n$, an array size of $2^{n}-1$ is needed.     * For a node at index $i$ ($1 \le i \le n$):         * parent(i) is at $\lfloor i/2 \rfloor$ if $i \ne 1$.         * left_child(i) is at $2i$ if $2i \le n$.         * right_child(i) is at $2i + 1$ if $2i + 1 \le n$.     * Disadvantages: Waste of space for skewed trees; difficulties in insertion/deletion.

• Linked Representation:     * Each node has three fields: left_child pointer, data, and right_child pointer.     * C Structure Definition: c typedef struct node *tree_pointer; typedef struct node { int data; tree_pointer left_child, right_child; };         

Binary Tree Traversals

• Definition: The process of visiting or displaying every node in a binary tree in a specific order.

• In-Order Traversal (left-root-right):     1. Recursively traverse left subtree.     2. Visit root node.     3. Recursively traverse right subtree.     * Example Order: $I - D - J - B - F - A - G - K - C - H$

• Pre-Order Traversal (root-left-right):     1. Visit root node.     2. Recursively traverse left subtree.     3. Recursively traverse right subtree.     * Example Order: $A - B - D - I - J - F - C - G - K - H$

• Post-Order Traversal (left-right-root):     1. Recursively traverse left subtree.     2. Recursively traverse right subtree.     3. Visit root node.     * Example Order: $I - J - D - F - B - K - G - H - C - A$

• Iterative In-Order Traversal:     * Uses an explicit stack to mimic recursion.     * Complexity: Time is $O(n)$, as each node is pushed/popped once. Space is $O(depth)$, which is $O(n)$ in the worst case.

• Level Order Traversal:     * Uses a queue (typically circular).     * Visit root, then root’s children from left to right, then grandchildren, etc.     * Process: Delete front, print data, add left child to queue, add right child to queue.

• Arithmetic Expression Trees:     * Infix: Result of in-order traversal (e.g., $A / B \times C \times D + E$).     * Prefix: Result of pre-order traversal (e.g., $+ \times \times / A B C D E$).     * Postfix: Result of post-order traversal (e.g., $A B / C \times D \times E +$).     * Level Order: (e.g., $+ \times E \times D / C A B$).

Binary Search Trees (BST)

• Definition: A binary tree (possibly empty) where:     1. Every element has a unique key.     2. Keys in the left subtree are smaller than the root key.     3. Keys in the right subtree are larger than the root key.     4. Left and right subtrees are also BSTs.

• Searching a BST:     * Algorithm: Start at root. If key matches, done. If search key is smaller, move to left subtree. If larger, move to right subtree.     * Complexity: Time is $O(h)$ where $h$ is height. Recursive search uses $O(h)$ stack space.

• Inserting into a BST:     * Locate the proper NULL location by following search logic and insert a new leaf node.     * Complexity: $O(\log n)$ on average; nodes are always inserted as leaf nodes.

• Deleting from a BST (Three Cases):     1. Case 1: Leaf Node: Find the node, set the parent's link to NULL, and free the node.     2. Case 2: Node with One Child: Link the node's single child directly to its parent, then free the node.     3. Case 3: Node with Two Children:         * Find either the largest node in the left subtree OR the smallest node in the right subtree.         * Swap the value of the node to be deleted with this found node.         * Delete the node from its new position (which will now fall into Case 1 or Case 2).     * Complexity: Deletion operation is performed with $O(\log n)$ time complexity.

• Height of BST Example Construction:     * Sequence: 10, 12, 5, 4, 20, 8, 7, 15, 13.     * Resulting BST Structure:         * 10 is root.         * 5 is left of 10; 12 is right of 10.         * 4 is left of 5; 8 is right of 5.         * 7 is left of 8.         * 20 is right of 12.         * 15 is left of 20; 13 is left of 15.