Table of Content

Introduction to Trees

• Definition: Trees are hierarchical data structures, distinct from linear data structures like arrays, stacks, queues, and linked lists. In a tree, data is organized in a hierarchy, forming parent-child relationships that resemble a tree's branches.
• Real-Life Examples:
  • Family Tree: Represents family relationships, starting from ancestors at the top and branching down to descendants.
  • Computer Folder Structure: Folders contain files and other subfolders, forming a hierarchical organization.
• Key Components:
  • Root: The topmost node in a tree, from which all other nodes descend.
  • Edges: Connections between nodes that represent relationships (parent-child).
  • Nodes: Individual elements of a tree, each holding data and references to its children.
  • Leaf Nodes: Nodes that do not have any children, representing the end of a branch.

Why Use Trees?

Basic Tree Terminology

Binary Trees

• Definition: A binary tree is a specific type of tree where each node has at most two children, referred to as the left child and the right child. This restriction leads to various properties and algorithms specific to binary trees.
• Structure:
  • Root: The initial node where the tree begins.
  • Left and Right Child: The two potential child nodes that any given node can have.
  • Leaf Nodes: Nodes without any children, marking the end of a particular branch of the tree.
  • Edge: A connection between a parent node and its child, representing the relationship.

Types of Binary Trees

Tree Traversal Techniques

• Traversal: The process of visiting all the nodes in a tree in a specific order.
• Depth-First Search (DFS):
  • Pre-order: Visit the root node first, then recursively traverse the left subtree, followed by the right subtree. Suitable for copying or evaluating expressions.
  • In-order: Recursively traverse the left subtree first, visit the root node, and then traverse the right subtree. This traversal of a binary search tree results in sorted order.
  • Post-order: Recursively traverse the left subtree, then the right subtree, and finally visit the root node. Useful for deleting a tree or evaluating postfix expressions.
• Breadth-First Search (BFS):
  • Level-Order: Traverse the tree level by level, starting from the root and moving down to the lower levels. BFS is implemented using a queue and is useful for finding the shortest path in an unweighted graph.