• Definition: A tree is a connected, undirected graph with no cycles. It is a special type of graph.
• Properties:
  • A tree with \(n\) vertices has exactly \(n-1\) edges.
  • There is exactly one path between any two nodes in a tree.
• Types of Trees:
  • Binary Tree: Each node has at most two children.
  • Binary Search Tree (BST): A binary tree where the left child is smaller and the right child is larger than the parent node.
  • Balanced Tree: A tree where the height difference between subtrees is minimal.
• Key Terminologies:
  • Root: The topmost node in a tree.
  • Leaf: A node with no children.
  • Height of Tree: The number of edges on the longest path from the root to a leaf.
  • Subtree: A tree consisting of a node and its descendants.