Concept

Non-linear Structure: Unlike linear data structures such as arrays, linked lists, stacks, and queues, which store data sequentially, a tree is a non-linear data structure. This means that data in a tree is organized hierarchically, allowing for quicker and easier access to the data.

Definition:

• A tree is a recursive data structure consisting of one or more nodes.
• One node is designated as the root of the tree, from which all other nodes are reachable.
• The nodes other than the root node are referred to as children of the root. These nodes can further have their own children, forming a hierarchical structure.
• Each non-root node is part of a sub-tree, which is a smaller tree within the overall tree structure.
• Nodes maintain parent-child relationships, where each node (except the root) has exactly one parent and zero or more children.
• Nodes that share the same parent are called siblings.

General Tree Properties:

• A node in a general tree can have any number of children.
• However, each node can have only one parent.
• The root node serves as the starting point for accessing the entire tree structure.

Example:

The provided image illustrates an example of a tree data structure.

• In the image, node A is the root node of the tree, while nodes B, C, and D are its children. nodes B,C and D are sibling nodes
• Each child node may further have its own children, forming a hierarchical structure.

Most commonly used Tree Terminologies:

Node: A node is a fundamental component of a tree data structure. It represents a single element within the tree and may contain some associated data. Each node in a tree has zero or more child nodes connected to it via edges.

Edge: An edge is a connection between two nodes in a tree. It represents the relationship between a parent node and its child node. Edges define the paths along which data can be accessed or traversed within the tree.

Root: The root is the topmost node of a tree. It serves as the starting point for accessing the entire tree structure. A tree has exactly one root node, and it is the only node in the tree that has no parent.

Height of a Node: The height of a node in a tree is the length of the longest path from that node to a leaf node. In other words, it is the number of edges on the longest downward path from the node to a leaf. The height of a leaf node is typically considered to be 0.

Depth of a Node: The depth of a node in a tree is the length of the path from the root node to that particular node. It is the number of edges on the path from the root to the node. The depth of the root node is typically considered to be 0.

Height of a Tree: The height of a tree is the maximum depth of any node in the tree. It represents the length of the longest path from the root node to a leaf node. The height of an empty tree is conventionally considered to be -1..

Degree of a Node: The degree of a node in a tree is the number of children it has. For example, a node with no children (a leaf node) has a degree of 0, while a node with three children has a degree of 3.

Forest: A forest is a collection of disjoint trees. In other words, it is a set of trees where there is no common root among them. Each individual tree within a forest follows the structure and properties of a tree data structure.

Tree Applications

• Binary Search Trees(BSTs) are used to quickly check whether an element is present in a set or not.
• Heap is a kind of tree that is used for heap sort.
• A modified version of a tree called Tries is used in modern routers to store routing information.
• Most popular databases use B-Trees and T-Trees, which are variants of the tree structure we learned above to store their data
• Compilers use a syntax tree to validate the syntax of every program you write.