A Tree is a non-linear data structure used to organize information in a hierarchical manner. Unlike arrays, stacks, queues, and linked lists, where elements are generally arranged in a linear sequence, a tree represents relationships through branches and parent-child connections.
Trees are useful whenever data naturally contains different levels or categories. Computer folders, organization charts, website menus, HTML documents, database indexes, and expression structures are common examples where tree-like relationships can be found.
Tree data structures are also the foundation of several advanced structures such as Binary Search Trees, AVL Trees, Heaps, B-Trees, B+ Trees, Tries, and Expression Trees.
A tree is a collection of nodes connected by edges in which the nodes are arranged in a hierarchical structure. The topmost node is called the root, and the nodes below it are connected through parent-child relationships.
A tree does not contain cycles. In a non-empty tree, every node except the root has exactly one parent. If a tree contains N nodes, it contains exactly N - 1 edges.
A Tree is a hierarchical, non-linear data structure in which nodes are connected through edges and one node acts as the root of the structure.
A
/ \
B C
/ \ / \
D E F G
In the above tree:
Many types of information have a natural hierarchy. A simple linear structure may represent the individual elements, but it does not clearly express the relationships between different levels.
Trees solve this problem by representing information as branches. Depending on the type of tree, they can also support specialized searching, ordering, indexing, prioritization, and decision-making.
A node is an individual element of a tree. It normally stores a data value and references to one or more related nodes.
An edge is a connection between two nodes. It represents a direct relationship between a parent and its child.
The root is the starting node of a non-empty tree. It does not have a parent.
A subtree is a smaller tree consisting of a node and all of its descendants.
Understanding tree terminology makes it easier to study Binary Trees, Binary Search Trees, AVL Trees, Heaps, and other tree-based structures.
The root is the topmost node of a tree. A non-empty tree contains exactly one root node.
A
/ \
B C
Here, A is the root node.
A node that has one or more children is called a parent node.
In the above example, A is the parent of B and C.
A node directly connected below another node is called its child.
B and C are children of A.
Nodes that have the same parent are called sibling nodes.
B and C are siblings because both have A as their parent.
A node that has no children is called a leaf node or terminal node.
A
/ \
B C
/ \ / \
D E F G
D, E, F, and G are leaf nodes.
An internal node is a node that has at least one child.
In the above tree, A, B, and C are internal nodes.
The degree of a node is the number of children directly connected to that node.
A
/ | \
B C D
Degree of A = 3.
The degree of a tree is the maximum degree of any node present in the tree.
The depth of a node is the number of edges between the root and that node.
A
/ \
B C
/
D
Depth of A = 0, Depth of B = 1, and Depth of D = 2.
Level indicates the position of a node within the hierarchy. Some textbooks consider the root to be level 0, while others consider it level 1. The chosen convention should therefore be stated when solving a problem.
The height of a node is the number of edges on the longest downward path from that node to a leaf.
The height of a non-empty tree is the height of its root node. It represents the longest path from the root to any leaf.
An ancestor of a node is any node that occurs on the path from the root to that node, excluding the node itself.
A descendant is a node that occurs below another node in the tree.
Different tree structures use different rules to organize their nodes. Some allow an unlimited number of children, while others restrict the number of children or maintain an ordering rule for efficient operations.
A General Tree is a tree in which a node can have any number of children. There is no fixed maximum number of children.
A
/ | \
B C D
/ \ |
E F G
General trees are useful for representing structures where different nodes may have different numbers of children.
A Binary Tree is a tree in which each node can have at most two children. These are normally called the left child and right child.
A
/ \
B C
/ \ \
D E F
A binary tree node may have zero, one, or two children.
A Full Binary Tree is a binary tree in which every node has either zero children or exactly two children.
A
/ \
B C
/ \ / \
D E F G
No node in this example has exactly one child, so it is a full binary tree.
A Complete Binary Tree has every level completely filled except possibly the last level. Nodes on the final level are placed from left to right.
A
/ \
B C
/ \ /
D E F
Complete binary trees are especially important in heap implementations.
A Perfect Binary Tree is a binary tree in which every internal node has exactly two children and every leaf is located at the same level.
A
/ \
B C
/ \ / \
D E F G
A Balanced Binary Tree maintains a controlled difference between the heights of its subtrees. The exact balance condition depends on the particular balanced-tree implementation.
Maintaining a small height is important because many tree operations depend directly on the height of the tree.
A Degenerate Tree is a tree in which each parent has only one child. As a result, the structure becomes similar to a linked list.
A | B | C | D | E
A degenerate structure has a large height relative to the number of nodes and may therefore provide poor performance for height-dependent operations.
A Skewed Binary Tree is a binary tree in which nodes continue mainly in one direction.
A
/
B
/
C
/
D
A
\
B
\
C
\
D
A Binary Search Tree is a binary tree that maintains an ordering relationship between the values stored in its nodes.
Under the standard BST convention, values smaller than a node are stored in its left subtree and values greater than the node are stored in its right subtree.
50
/ \
30 70
/ \ / \
20 40 60 80
Searching begins at the root. The target value is compared with the current node, and the comparison determines which subtree should be examined next.
If target = current node
→ Element found
If target < current node
→ Move to left subtree
If target > current node
→ Move to right subtree
For example, searching for 60 in the following tree follows the path:
50 → 70 → 60
A new value is inserted by following the BST ordering rule until an empty position is reached.
Suppose 65 is inserted into the following tree:
50
\
70
/
60
The value 65 is greater than 50, smaller than 70, and greater than 60. Therefore, it becomes the right child of 60.
50
\
70
/
60
\
65
Deletion is more involved than insertion because the BST ordering property must remain valid after removing a node.
A leaf has no children, so it can be removed directly.
When a node has one child, that child takes the position of the deleted node.
When a node has two children, its value is commonly replaced by the inorder successor or inorder predecessor. The replacement node is then removed from its original position.
| Operation | Average Case | Worst Case |
|---|---|---|
| Search | O(log n) | O(n) |
| Insertion | O(log n) | O(n) |
| Deletion | O(log n) | O(n) |
The average-case logarithmic performance depends on the tree remaining reasonably balanced. A highly skewed BST can have height close to n, resulting in O(n) operations.
Tree Traversal is the process of visiting the nodes of a tree in a particular order. Traversal is required for processing, searching, displaying, copying, deleting, and evaluating tree structures.
A
/ \
B C
/ \ / \
D E F G
In Preorder Traversal, the root is processed first, followed by the left subtree and then the right subtree.
Root → Left → Right
Result:
A → B → D → E → C → F → G
Preorder traversal can be useful for copying a tree and creating structural representations of a tree.
In Inorder Traversal, the left subtree is processed first, followed by the root and then the right subtree.
Left → Root → Right
Result:
D → B → E → A → F → C → G
Inorder traversal of a BST produces its keys in sorted order when the standard BST ordering rule is used.
In Postorder Traversal, the left subtree is processed first, followed by the right subtree and finally the root.
Left → Right → Root
Result:
D → E → B → F → G → C → A
Postorder is useful when child nodes must be processed before their parent, such as during tree deletion.
Level Order Traversal visits nodes level by level, starting at the root. It is also called Breadth First Traversal.
A queue is commonly used to implement level-order traversal because nodes must be processed in the order in which they are discovered.
A → B → C → D → E → F → G
| Traversal | Order | Common Use |
|---|---|---|
| Preorder | Root → Left → Right | Copying and serialization |
| Inorder | Left → Root → Right | Sorted BST output |
| Postorder | Left → Right → Root | Deletion and expression processing |
| Level Order | Level by level | Hierarchical processing |
An AVL Tree is a self-balancing Binary Search Tree. It automatically maintains its height within a controlled range after insertion and deletion.
AVL is named after Georgy Adelson-Velsky and Evgenii Landis, who introduced the structure.
For every node in an AVL tree, the difference between the heights of its left and right subtrees must not be greater than one.
The balance factor of a node is calculated as:
Balance Factor = Height of Left Subtree - Height of Right Subtree
The permitted balance factors in an AVL tree are:
-1 0 +1
If a node obtains a balance factor outside this range after an update, the tree must be rebalanced.
Rotations are local restructuring operations that restore AVL balance while preserving the ordering property of the Binary Search Tree.
An LL imbalance occurs when the heavy path goes through the left child and then its left child. A right rotation is used.
An RR imbalance occurs when the heavy path goes through the right child and then its right child. A left rotation is used.
An LR imbalance occurs when the path goes left and then right. It is corrected using a left rotation followed by a right rotation.
An RL imbalance occurs when the path goes right and then left. It is corrected using a right rotation followed by a left rotation.
| Operation | Time Complexity |
|---|---|
| Search | O(log n) |
| Insertion | O(log n) |
| Deletion | O(log n) |
Trees are used in many areas of computer science because they are well suited to hierarchical and branching information.
Operating systems organize directories and subdirectories in a hierarchical manner. A directory may contain files and additional directories.
Root ├── Documents │ ├── Notes │ └── Projects ├── Pictures └── Downloads
Database systems use specialized tree structures such as B-Trees and B+ Trees to organize indexes and reduce the amount of storage access needed for large datasets.
Web browsers represent HTML documents using a Document Object Model. Elements form parent-child relationships that can be represented as a tree.
HTML
├── HEAD
└── BODY
├── HEADER
└── MAIN
Compilers use syntax-related tree structures to represent and analyze the organization of source code.
Expression trees represent mathematical and logical expressions using operators and operands.
Decision trees represent a sequence of conditions and possible outcomes. They are used in machine learning and rule-based systems.
Heap structures are based on complete binary trees and are commonly used to implement priority queues.
Website categories, menus, organizational structures, and similar systems can be represented using tree-like relationships.
An Expression Tree is a binary tree used to represent an expression. Operators are generally stored in internal nodes and operands are stored at leaf nodes.
*
/ \
+ 5
/ \
2 3
The above tree represents:
(2 + 3) * 5
| Tree | Linked List |
|---|---|
| Hierarchical or branching structure | Primarily linear structure |
| Nodes may have multiple children | Nodes normally follow a next-node relationship |
| Useful for hierarchical information | Useful for sequential collections |
| Traversal depends on tree structure | Usually traversed sequentially |
| Can support specialized searching | Sequential searching is commonly used |
| Tree | Graph |
|---|---|
| Connected and acyclic | May contain cycles |
| Has a root when treated as a rooted tree | Does not require a root |
| N nodes have N - 1 edges | Number of edges can vary |
| Exactly one path between two nodes | Multiple paths may exist |
| Usually represents hierarchy | Represents general relationships |
| Traversal | Time Complexity | Typical Extra Space |
|---|---|---|
| Preorder | O(n) | O(h) |
| Inorder | O(n) | O(h) |
| Postorder | O(n) | O(h) |
| Level Order | O(n) | O(w) |
Here, n is the number of nodes, h is the tree height, and w is the maximum width of the tree.
A tree is a non-linear data structure that organizes nodes in a hierarchy using parent-child relationships. A non-empty tree has one root and contains no cycles.
A general tree does not place a fixed maximum on the number of children a node can have. A binary tree allows each node to have at most two children.
A Binary Search Tree is a binary tree that maintains an ordering relationship between node values. Smaller values are placed in the left subtree and larger values in the right subtree under the standard BST convention.
A full binary tree is a binary tree where every node has either zero children or exactly two children.
A complete binary tree has all levels completely filled except possibly the last, and the final level is filled from left to right.
A perfect binary tree has two children for every internal node and all leaf nodes occur at the same level.
If insertions create a highly skewed BST, the height can become close to the number of nodes. In that situation, search, insertion, and deletion can take O(n) time.
Tree traversal is the process of systematically visiting nodes in a tree. Common methods include preorder, inorder, postorder, and level-order traversal.
Inorder traversal produces the values of a standard BST in sorted order.
An AVL Tree is a self-balancing Binary Search Tree that keeps the height difference between the left and right subtrees of every node within one.
AVL rotations are restructuring operations used to restore balance after an insertion or deletion. The four standard cases are LL, RR, LR, and RL.
Trees are used in file systems, database indexing, HTML DOM structures, compilers, expression processing, decision systems, priority queues, and many other software applications.
Tree Data Structure is an important non-linear structure for representing hierarchical and branching information. Its basic concepts include nodes, edges, root, parent, child, leaf, depth, height, and subtree.
Binary Trees introduce the concept of left and right children, while Binary Search Trees add an ordering rule that can make searching and updating more efficient when the tree remains well shaped.
Tree traversal provides systematic methods for visiting every node, including preorder, inorder, postorder, and level-order traversal. AVL Trees take the concept further by automatically maintaining balance after updates.
A solid understanding of trees provides the foundation for advanced structures such as heaps, B-Trees, B+ Trees, Tries, Segment Trees, and other specialized data structures used in real-world software systems.