Lecture 262:- Trees Terminology

Trees are hierarchical data structures that consist of nodes connected by edges. Each tree has a root node, which is the topmost node, and every node in the tree has a parent node (except for the root node) and zero or more child nodes. Here are some commonly used terms and concepts related to trees:

1. Node: Each element in a tree is called a node. Each node contains data and a reference to its child nodes (if any) and its parent node (except for the root node).
2. Root: The topmost node of the tree is called the root. It is the starting point of the tree and has no parent.
3. Parent: A node is the parent of its child nodes. It is the node from which the child nodes originate.
4. Child: Nodes that are directly connected to a parent node are called its child nodes.
5. Sibling: Nodes that have the same parent node are called siblings. They share the same parent.
6. Leaf: A leaf node is a node that has no children; it is the terminal node in a tree.
7. Depth: The depth of a node in a tree is the number of edges from the root node to that node.
8. Height: The height of a tree is the number of edges in the longest path from the root node to a leaf node. Alternatively, the height of a node is the number of edges in the longest path from that node to a leaf node.
9. Subtree: A subtree is a tree formed by a node and all its descendants.
10. Binary Tree: A binary tree is a tree in which each node has at most two children, referred to as the left child and the right child.
11. Binary Search Tree (BST): A binary search tree is a binary tree in which for each node, all nodes in its left subtree have values less than the node's value, and all nodes in its right subtree have values greater than the node's value.
12. Balanced Tree: A balanced tree is a tree in which the difference in height between the left and right subtrees of any node is at most one. Examples include AVL trees and Red-Black trees.
13. Complete Binary Tree: A complete binary tree is a binary tree in which all levels are completely filled except possibly the last level, and the last level is filled from left to right.
14. Full Binary Tree: A full binary tree is a binary tree in which every node has either 0 or 2 children.
15. Perfect Binary Tree: A perfect binary tree is a binary tree in which all internal nodes have two children, and all leaf nodes are at the same level.
16. Forest: A collection of disjoint trees is called a forest.

These are some of the fundamental terms and concepts related to trees. Trees are widely used in computer science and various algorithms and data structures are based on tree concepts.