Data Structures - Trees

Trees

Overview

• Trees are versatile data structures used to solve a wide array of problems.
• They organize data in a hierarchical structure.
• A tree is a collection of nodes:
  • It has a root node.
  • The remaining nodes are divided into disjointed subsets, each a tree itself, known as subtrees.

Basic Terminologies

• Root: A special node in a tree that serves as the starting point in the hierarchy. Example: 'A' in the figure.
• Node: A data item within the tree, holding data and links (branches) to other data items.
• Levels: The tree is structured in levels, with the root at level 0. Children of a node at level $n$ are at level $n+1$.
• Level of a node: The number of edges from the root to that node.
• Depth/Height: The maximum level of any node in the tree, indicating the longest path from the root to a leaf node.
• Degree of a node: The number of subtrees a node has. Examples:
  • Degree of node A is 3.
  • Degree of node B is 2.
  • Degree of node D is 3.
  • Degree of node J is 4.
• Degree of a tree: The maximum degree of any node in the tree. If Node J has a degree of 4, and all other nodes have less than or equal to degree, then the degree of the tree is 4.
• Terminal node/Leaf: A node with a degree of zero (no subtrees). Examples: M, N, I, O, etc.
• Non-terminal node: A node with a degree greater than zero.

Types of Trees

• General Tree
• Forests
• Binary Tree
• Binary Search Tree
• Expression Tree
• Tournament Tree

Binary Tree

• A tree where each node has at most two children.
• A binary tree can be:
  1. An empty tree.
  2. A node (root) with two children (left and right), each of which is a binary tree.
• Links between nodes are called edges.

Binary Tree Vs General Tree

Full Binary Tree

• Each node has two children, except for the leaf nodes on the last level.

Complete Binary Tree

• A binary tree that is either:
  • A full binary tree, OR
  • A tree that would be full, but is missing rightmost nodes on the last level.
• A full binary tree is also a complete binary tree.

Expression Tree

• A binary tree with specific properties:
  • Leaves are operands (e.g., a, b, c, 6, 100).
  • Root and internal nodes are operators (e.g., +, -, *, /, ^).
  • Subtrees represent subexpressions with the root being the operator.

Expression Tree Examples

• Example 1: Expression tree for $(A+B)*C$
• Example 2: Expression tree for $A + B*C$
• Example 3: Expression tree for $3 + 7 \times 2 - 1$

Tree Traversal Techniques

• Visiting or accessing each node of the tree exactly once in a specific order.
• Traversal algorithms help process all tree nodes.
• Since trees are non-linear, multiple traversal orders are possible.
• Methods:
  • Depth-First Search (DFS):
    1. Preorder Traversal
    2. Inorder Traversal
    3. Postorder Traversal
  • Level Order Traversal / Breadth-First Search (BFS)

1. Preorder Traversal

• Order: Root -> Left -> Right
• Example: 1 → 2 → 4 → 5 → 3 → 6
• Example: 9 5 3 1 4 8 6 20 12 10 11 30 21 31

2. Inorder Traversal

• Order: Left -> Root -> Right
• Example: 4 → 2 → 5 → 1 → 3 → 6
• Example: 1 3 4 5 6 8 9 10 11 12 20 21 30 31

3. Postorder Traversal

• Order: Left -> Right -> Root
• Example: 4 5 → 2 → 6 3 1
• Example: 1 4 3 6 8 5 11 10 12 21 31 30 20 9

Assignments

• Assignment 1: Draw an expression tree for $a + (b * c) + (e + f) * d$, and let $a = 5$, $b = 2$, $c = 1$, $d = 0$, $e = 4$, $f = 10$. Find the result using the tree.
• Assignment 2: Determine In-Order, Pre-Order, and Post-Order traversals for a given tree.