Basic Terminologies in Trees
Tree:
A Tree is a hierarchical data structure consisting of nodes, where each node has a value and references to child nodes. Trees are widely used in computer science for organizing data for efficient searching, insertion, and deletion.
Basic Terminologies in Trees:
Node:
A node is a basic unit of a tree that contains data (or a value) and references to its children.
Example: In a tree of integers, each node stores an integer value.
Root:
The root is the topmost node of the tree.
It has no parent.
A tree has exactly one root.
Example: In a family tree, the ancestor is the root.
Edge:
An edge is a connection between two nodes.
It represents the parent-child relationship.
The number of edges in a tree is always equal to the number of nodes minus one.
Parent:
A parent node is a node that has child nodes.
Example: In a binary tree, a node with two subtrees has two children.
Child:
A child is a node that descends from a parent node.
Example: If node A points to node B, then node B is a child of node A.
Sibling:
Siblings are nodes that share the same parent.
Example: In a binary tree, the left and right children of the same node are siblings.
Leaf (External Node):
A leaf is a node with no children.
It is the terminal node of a tree.
Example: In a tree representing a company hierarchy, employees with no subordinates are leaf nodes.
Internal Node:
An internal node is a node with at least one child.
All nodes except the root and leaves are internal nodes.
Ancestor:
An ancestor of a node is any node along the path from the root to that node.
Example: In a family tree, a grandparent is an ancestor.
Descendant:
A descendant is a node that can be reached from a given node by moving downward.
Example: A child, grandchild, or great-grandchild are descendants of a node.
Degree:
The degree of a node is the number of children it has.
Example: In a binary tree, each node can have a degree of 0, 1, or 2.
Level:
The level of a node is its depth from the root.
The root is at level 0, its children are at level 1, and so on.
Height of a Node:
The height of a node is the number of edges on the longest path from the node to a leaf.
Example: A node with no children has a height of 0.
Height of a Tree:
The height of a tree is the height of the root node.
It represents the maximum depth of the tree.
Depth of a Node:
The depth of a node is the number of edges from the root to that node.
Example: The root has a depth of 0.
Path:
A path is a sequence of nodes connected by edges.
Example: In a binary tree, a path from the root to a leaf node might be represented as Root → Left → Right.
Subtree:
A subtree is any connected part of the tree that forms a tree itself.
Example: If node B is a child of node A, the subtree rooted at B consists of B and its descendants.
Binary Tree:
- A binary tree is a type of tree in which each node has at most two children, known as the left child and the right child.
Forest:
- A forest is a collection of disjoint trees.
Null Tree:
- A null tree is an empty tree with no nodes.
Balanced Tree:
- A tree is balanced if the difference in height between the left and right subtrees of any node is at most 1.
Complete Tree:
- A complete tree is a tree where all levels are fully filled except possibly the last, and all nodes in the last level are as far left as possible.
Full Tree:
- A full tree is a tree where every node has either 0 or the maximum number of children (e.g., 2 in a binary tree).
Perfect Tree:
- A perfect tree is a type of full tree in which all leaf nodes are at the same level, and all internal nodes have the maximum number of children.
Binary Search Tree (BST):
- A binary search tree is a binary tree in which the left child contains only nodes with values less than the parent node, and the right child contains only nodes with values greater than the parent node.