IB Computer Science 5.1.8 Trees Notes

Trees

While you imagine forest, trees are a fundamental data structure in computer science, used to represent hierarchical data.

Terminology

1. Root has no parent.
2. All other nodes are descendants of the root.
3. There is always exactly one root node.

Each node (except the root) has exactly one parent.

Example

For instance, here:

• Node A (marked green) is root.
• Nodes B and C are children of node A.
• Node A is parent of B and C
• Nodes D and E are leaves.

Practical Applications of Binary Trees

1. Binary Search Trees (BSTs)
   1. Organize data for efficient searching, insertion, and deletion.
   2. Left child nodes contain values less than the parent.
   3. Right child nodes contain values greater than or equal to the parent.
2. Expression Trees
   1. Represent mathematical expressions.
   2. Operators are stored in parent nodes.
   3. Operands are stored in leaf nodes.
3. Trie
   1. A specialized tree for fast string searching.
4. Decision Trees
   1. Used in machine learning for decision-making processes.
   2. Each node represents a decision or condition.

Logical Operations on Trees

While insertion (adding new nodes) and deletion (removing nodes) operation in trees can be not specifically defined, some cases line BST has well defined process:

1. Binary Search Tree (BST) Insertion:
   1. Start at the root.
   2. Compare the value to be inserted with the current node.
   3. Move left if the value is smaller, right if larger.
   4. Repeat until a null position is found, then insert the node.
2. Binary Search Tree (BST) deletion:
   1. Deleting a leaf node:
      1. Simply remove the node.
   2. Deleting a node with one child:
      1. Remove the node and replace it with its child.
   3. Deleting a node with two children:
      1. Find the in-order successor (the smallest value in the right subtree) or in-order predecessor (the largest value in the left subtree).
      2. Replace the value of the node to be deleted with the successor (or predecessor).
      3. Delete the successor (or predecessor) node, which will fall into case 1 or 2.

While BST insertion is straightforward, deletion involves more steps and is more complex.

Binary Tree Traversal Orders

Tree traversals is essential for tasks like searching, sorting, and manipulating data stored in trees.

There are three primary types of tree traversal:

1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal

Each traversal method follows a unique pattern, which we'll explore in detail.

In-order Traversal

In-order traversal visits nodes in the following order:

1. Traverse the left subtree.
2. Visit the current node.
3. Traverse the right subtree.

def inOrder(node):
    if node is None:
        return
    inOrder(node.left) # Traverse left subtree
    print(node.value)
    inOrder(node.right) # Traverse right subtree

This traversal is particularly useful for binary search trees, as it visits nodes in ascending order.

Pre-order Traversal

Pre-order traversal visits nodes in the following order:

1. Visit the current node.
2. Traverse the left subtree.
3. Traverse the right subtree.

def preOrder(node):
    if node is None:
        return
    print(node.value)
    preOrder(node.left) # Traverse left subtree
    preOrder(node.right) # Traverse right subtree

Pre-order traversal is useful for creating a copy of the tree or for problems where the root must be processed before its subtrees.

Post-order Traversal

Post-order traversal visits nodes in the following order:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the current node.

def postOrder(node):
    if node is None:
        return
    postOrder(node.left) # Traverse left subtree
    postOrder(node.right) # Traverse right subtree
    print(node.value)

Post-order traversal is often used when deleting nodes in a tree or evaluating expression trees, because it processes children before the parent.