Binary Trees and Their Types

Binary Tree

• Recursive function inOrder() traverses a binary tree using in-order traversal.
• The function takes a process function as an argument, and then recursively calls itself on each child node before executing the process function.
• inOrder() ensures the order of execution: left child, process, right child.

Binary Tree as an Array

• The binary tree can be represented as an array, with the root node at position 0.
• Parent node is at array index (i - 1) / 2, where i is the index of the current node.
• Left child is at array index 2 * i + 1, and right child at 2 * i + 2.

Other Types of Trees

• There are several types of trees beyond binary search trees, including full trees, complete trees, heaps, and B-trees.

Full Binary Tree

• Every node in a full binary tree has two children or no children.

Complete Binary Tree

• Complete binary tree has all levels filled except possibly the last level, which is filled from left to right.

Heap

• Heap is a complete binary tree that follows max-heap property or min-heap property.
• Max-heap property: Every node is greater than its children.
• Min-heap property: Every node is smaller than its children.
• Heapify is the process of turning a binary tree into a heap.
• Re-heapification upward: Adding an element to the heap.
• Re-heapification downward: Removing an element from the heap.

B-Tree

• B-tree is a self-balancing search tree where each node can contain multiple keys and have multiple children.
• Used with large amounts of data where disk access often occurs.
• Optimizes disk accesses by storing multiple keys in a single node.
• Properties of B-tree:
  • Keys are stored in increasing order within each node.
  • Internal non-leaf nodes have at least MAX/2 and at most MAX children.
  • All leaf nodes have the same depth.
  • The root has at least two children and one key.

Passing a Function as an Argument

• To process data in a generic way without sacrificing type-specific instructions, a function can take another function as an argument.
• Placeholders are used in the prototype and function header to define the function signature, like returnType placeHolderName(dataType, …)

Binary Tree Traversal: Generic process

• inOrder() can take a function as an argument, allowing flexible processing of node data during tree traversal.
• Template-based approach allows customization for specific data types without modifying the generic inOrder() function.
• process is a placeholder for the function that's passed as an argument to inOrder().

Binary Tree Traversal

• In-order: The left subtree is traversed, then the current node is processed, and finally the right subtree is traversed.
• Example: 1, 2, 4, 5, 3
• Pre-order: The current node is processed, then the left subtree is traversed, and finally the right subtree is traversed.
  • Example 4, 2, 5, 1, 3
• Post-order: The left subtree is traversed, then the right subtree is traversed, and finally the current node is processed.
  • Example 3, 1, 5, 2, 4
• Backward in-order: The right subtree is traversed, then the current node is processed, and finally the left subtree is traversed.
  • Example 4, 5, 2, 3, 1

Binary Search Tree

• All nodes in the left subtree are less than or equal to the parent node.
• All nodes in the right subtree are greater than the parent node.

Explore the concepts of binary trees, including in-order traversal and their representation as arrays. Learn about different types of trees such as full binary trees, complete binary trees, and heaps. This quiz covers essential tree structures and their properties.