Trees are fundamental data structures that represent hierarchical relationships. They consist of nodes connected by edges, with each node storing data and references to other nodes. Understanding tree concepts is crucial for organizing and efficiently accessing information in computer science.

Trees come in various types, including binary trees and binary search trees, each with specific properties. Relationships between nodes, such as paths and common ancestors, play a vital role in tree operations. Traversal methods allow systematic exploration of tree structures, enabling efficient data manipulation and analysis.

Tree Fundamentals

Fundamental concepts of trees

• Tree represents a hierarchical data structure composed of nodes connected by edges
  • Acyclic property ensures no cycles or loops exist within the structure
  • Directed edges establish a specific direction from parent to child nodes
• Node serves as the basic unit in a tree, storing data and references to other nodes
  • Root node sits at the topmost position in the tree hierarchy, lacking a parent
  • Parent node directly connects to and resides above another node
  • Child node directly connects to and resides below another node
    • Sibling nodes share a common parent node
  • Leaf (external node) represents a node without any children
  • Internal node signifies a node with at least one child
• Edge denotes a connection between two nodes, signifying a parent-child relationship
• Subtree constitutes a portion of a tree, including a node and all its descendants

Properties and characteristics of trees

• Depth indicates the number of edges from the root to a particular node
  • Level refers to nodes positioned at the same depth within the tree
    • Root node resides at level 0, its children at level 1, and so on
• Height represents the maximum depth of any node in the tree
  • Height of a node equals the number of edges on the longest path from the node to a leaf
  • Height of a tree corresponds to the height of the root node
• Degree denotes the number of children associated with a node
  • Degree of a tree signifies the maximum degree of any node within the tree

Tree Types and Relationships

Types of trees

• Binary tree restricts each node to have at most two children, designated as left and right child
  • Strict/proper binary tree mandates each node to have either 0 or 2 children
  • Complete binary tree requires all levels, except possibly the last, to be entirely filled, with nodes positioned as far left as possible
• Binary search tree (BST) adheres to specific properties:
  • Left subtree of a node contains only nodes with keys less than the node's key
  • Right subtree of a node contains only nodes with keys greater than the node's key
  • Both left and right subtrees must also satisfy BST properties
• Balanced tree maintains a height difference of at most one between the left and right subtrees of any node
  • Examples include AVL trees and Red-Black trees
  • Guarantees $O(\log n)$ time complexity for search, insertion, and deletion operations

Relationships between tree nodes

• Path represents a sequence of nodes and edges connecting a node with its descendant
  • Path length corresponds to the number of edges in a path
• Distance between two nodes equals the number of edges on the path connecting them
• Lowest common ancestor (LCA) identifies the deepest node that serves as an ancestor to both nodes
  • LCA helps determine the distance between two nodes
• Traversal involves visiting each node in a tree exactly once
  • Preorder traversal: visit root, then left subtree, followed by right subtree
  • Inorder traversal: visit left subtree, then root, followed by right subtree
  • Postorder traversal: visit left subtree, then right subtree, followed by root