Comprehensive Guide to N-ary and Binary Search Trees

Introduction to N-ary and Generic Trees

  • N-ary Tree Node Structure:

    • A node in an N-ary tree consists of a parent reference and multiple child references (Node 1, Node 2, …, Node n).
    • This structure allows each node to have more than two children, unlike a standard binary tree.

  • Generic (N-ary) Tree Representation:

    • The top-most node is the ROOT.
    • Depth (dd): Represents the level of a node within the tree.
    • d=0d=0: Root level.
    • d=1d=1: Children of the root.
    • d=2,3,4d=2, 3, 4: Subsequent levels.
    • Height of the Tree (hh): The maximum depth of any node in the tree. In the provided example, the maximum depth is 44, thus h=4h = 4.

Binary Tree Implementation with C

  • TreeNode Class Definition:

    • The class is defined as public class TreeNode<T> where T : IComparable<T>. This ensures that the generic type TT can be compared, which is essential for ordering operations.
    • Properties:
    • public T Value { get; set; }: Holds the data of the node.
    • public TreeNode<T>? Left { get; set; }: Reference to the left child.
    • public TreeNode<T>? Right { get; set; }: Reference to the right child.
    • public TreeNode<T>? Parent { get; set; }: Reference to the parent node.

  • Constructor:

    • public TreeNode(T value, TreeNode<T>? parent = null, TreeNode<T>? left = null, TreeNode<T>? right = null)
    • It initializes the Value, Parent, Left, and Right properties with the provided arguments.

  • Visual Schematic of a Binary Tree Node:

    • Every node contains a central Value, a pointer to its Parent above it, and two pointers (Left and Right) branching below it.

Properties and Characterization of Binary Trees

  • General Binary Tree Structure:

    • Includes a ROOT node.
    • Every node has at most two children.
    • Metrics for the example provided:
    • Depth levels range from d=0d=0 to d=4d=4.
    • The Height (hh) of the tree is 44.

  • Perfect Binary Tree:

    • Definition: A binary tree where all leaves are at the same level and all internal nodes have exactly two children.
    • Leaf Node Calculation: The number of leaves is determined by 2h2^h. For a tree with height h=3h=3, the number of leaves is 23=82^3 = 8.
    • Total Number of Nodes (NN):
    • For height h=3h=3: N=1+2+4+8=20+21+22+23=15N = 1 + 2 + 4 + 8 = 2^0 + 2^1 + 2^2 + 2^3 = 15.
    • General Formula: N=∑i=0h2iN = \textstyle\sum_{i=0}^{h} 2^i.
    • Using the geometric series sum formula: N=2h+1−1N = 2^{h+1} - 1.
    • Proof through manipulation:
      • N=1+2+22+...+2hN = 1 + 2 + 2^2 + ... + 2^h
      • 2×N=2+22+...+2h+2h+12 \times N = 2 + 2^2 + ... + 2^h + 2^{h+1}
      • (2×N)−N=2h+1−1(2 \times N) - N = 2^{h+1} - 1
      • N=2h+1−1N = 2^{h+1} - 1
    • Height in terms of Nodes: Since N≈2hN \thickapprox 2^h, the height can be approximated as h≈log2(N)h \thickapprox \text{log}_2(N).

Tree Traversal Methodologies

  • Breadth-First Traversal (Level Order):

    • Visits nodes level by level starting from the root.
    • Sequence Example: HDLBGJACFIKE.
    • Iterative Algorithm (Queue-based):
    1. Create a new Queue Q.
    2. Enqueue the root node.
    3. While Q.Count > 0:
      • currentNode = Q.Dequeue()
      • Read/Process currentNode.
      • Enqueue currentNode.Left (if not null).
      • Enqueue currentNode.Right (if not null).

  • Depth-First Traversal (DFS):

    • Explores as far as possible along each branch before backtracking.
    • Consists of three main types based on when the current node is processed:
    1. PreOrder Traversal (Root, Left, Right):
    • Sequence: HDBACGFELJIK.
    • Recursive Logic:
      • Read CurrentNode.
      • PreOrder-Traversal(CurrentNode.Left).
      • PreOrder-Traversal(CurrentNode.Right).
    • Iterative Logic (Stack-based):
      1. Create a new Stack S.
      2. Push root to S.
      3. While S.Count > 0:
        • currentNode = S.pop()
        • Read currentNode.
        • Push currentNode.Right (so it is processed later).
        • Push currentNode.Left (so it is processed next).
    1. InOrder Traversal (Left, Root, Right):
    • Sequence: A, B, C, D, E, F, G, H, I, J, K, L.
    • Recursive Logic:
      • InOrder-Traversal(CurrentNode.Left).
      • Read CurrentNode.
      • InOrder-Traversal(CurrentNode.Right).
    1. PostOrder Traversal (Left, Right, Root):
    • Sequence: ACBEFGDIKJLH.
    • Recursive Logic:
      • PostOrder-Traversal(CurrentNode.Left).
      • PostOrder-Traversal(CurrentNode.Right).
      • Read CurrentNode.

Binary Search Trees (BST)

  • Fundamental Property: For every node, values in the left subtree are smaller than the node's value, and values in the right subtree are larger than the node's value.
  • Search/Insert Logic:
    • Start at the ROOT.
    • If the target value is less than CurrNode.Value, move to CurrNode.Left.
    • If the target value is greater than CurrNode.Value, move to CurrNode.Right.
    • Repeat until the node is found or a null link is reached (where the new node should be inserted).
  • Insertion Example: Inserting values 50, 20, 10, 30, 40, 70, 60, 80 results in a structured BST where the root is 50, its left child is 20, and its right child is 70.
  • Traversal Result: Performing an InOrder Traversal on a Binary Search Tree always yields the values in sorted ascending order.

Binary Search Tree Deletion Scenarios

Deletion from a BST involves different handling based on the number of children the node-to-delete has.

  • Scenario 1: Deleting a Leaf Node (Zero Children):

    • Simply nullify the reference from the parent to the node being deleted.
    • Examples given: Deleting values 30, 24 (left of parent) or 11, 16 (right of parent).

  • Scenario 2: Deleting a Node with One Child:

    • The child of the node-to-delete takes the position of the deleted node in the parent's structure.
    • Logic for Node with Left Child Only:
    • If Node.Left != NULL and Node.Right == NULL:
      • If Node is its parent's left child, Node.Prev.Left = Node.Left.
      • If Node is its parent's right child, Node.Prev.Right = Node.Left.
      • Update the child's parent reference: Node.Left.Prev = Node.Prev.
    • Logic for Node with Right Child Only:
    • If Node.Left == NULL and Node.Right != NULL:
      • Update parent's reference to point to Node.Right.
      • Update Node.Right.Prev = Node.Prev.

  • Scenario 3: Deleting a Node with Two Children:

    • Requires finding a replacement node to maintain BST properties. There are two options:
    1. Using the Predecessor:
    • The Predecessor is the node with the largest value in the left subtree.
    • Finding Predecessor: Move to Left, then keep moving Right until the right reference is null.
    • Deletion Process:
      • Assign the value of the predecessor to the node being "deleted."
      • Delete the predecessor node (which is either a leaf or has one left child).
    1. Using the Successor:
    • The Successor is the node with the smallest value in the right subtree.
    • Finding Successor: Move to Right, then keep moving Left until the left reference is null.
    • Deletion Process:
      • Assign the value of the successor to the target node.
      • Recursively delete the successor node (which will have at most one right child).

Performance and Balanced Trees

  • Balanced Binary Search Tree:
    • A tree where the height is kept minimal.
    • Complexity:
    • Search, Insertion, and Deletion: O(log2(n))O(\text{log}_2(n)) or O(h)O(h).
    • nn represents the total number of nodes.
    • hh represents the height of the tree.
    • Maintaining a balanced tree is critical; if a tree becomes skewed (like a linked list), the complexity degrades from logarithmic to linear (O(n)O(n)).