A Tree is a non-linear data structure consisting of nodes connected by edges with a root node and hierarchical relationships.
A Binary Tree is a tree in which each node has at most two children (left and right).
A Binary Search Tree (BST) is a binary tree where:
- Left subtree contains values less than root
- Right subtree contains values greater than root
- Inorder (Left, Root, Right)
- Preorder (Root, Left, Right)
- Postorder (Left, Right, Root)
An AVL Tree is a self-balancing binary search tree where the balance factor is -1, 0, or +1.
A Heap is a complete binary tree that satisfies the heap property (min or max).
A Min Heap is a heap where the parent node is smaller than its children.
A Max Heap is a heap where the parent node is greater than its children.
The height of a tree is the number of edges on the longest path from the root to a leaf node.
A Threaded Binary Tree is a binary tree where NULL pointers are replaced with links to inorder predecessor or successor.
A tree is a non-linear hierarchical structure made up of nodes and edges, and the tree-related topics in your notes include tree traversal, BST, AVL tree, threaded binary tree, and applications of trees.
A tree is a collection of nodes connected by edges in a hierarchical manner. It starts from a root node and extends into subtrees.
A node is an element of a tree that stores data.
The topmost node of the tree. It has no parent.
A connection between two nodes.
A node that has one or more children.
A node directly connected below a parent.
Nodes having the same parent.
A node with no children.
A node with at least one child.
The number of children of a node.
The maximum degree among all nodes in the tree.
The number of edges from root to the node.
The length of the longest path from a node to a leaf.
The number of edges from the root to a node.
A part of a tree formed by a node and all its descendants.
Tree is hierarchical.
One node is selected as root.
Every node except root has exactly one parent.
Leaf nodes do not have children.
Tree traversal methods are explicitly included in your unit notes, where inorder, preorder, and postorder traversals are discussed with algorithms and examples.
Tree traversal means visiting every node of a tree exactly once in a systematic order.
The three main traversals are:
1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal
In inorder traversal, the order is:
Left Subtree → Root → Right Subtree
D → B → E → A → C → F
In preorder traversal, the order is:
Root → Left Subtree → Right Subtree
A → B → D → E → C → F
In postorder traversal, the order is:
Left Subtree → Right Subtree → Root
D → E → B → F → C → A
| Traversal | Order |
|---|---|
| Inorder | Left, Root, Right |
| Preorder | Root, Left, Right |
| Postorder | Left, Right, Root |
Inorder: binary search tree gives sorted output
Preorder: copying tree
Postorder: deleting tree, evaluating expressions
BST operations such as insertion, deletion, and searching are clearly part of your notes and syllabus material.
A Binary Search Tree is a binary tree in which:
left subtree contains only smaller values
right subtree contains only larger values
For every node:
Left subtree < Root < Right subtree
Insert 25 into the tree:
25 < 50 → go left
25 < 30 → go left
25 > 20 → go right
Insert at correct position
Search 60:
60 > 50 → right
60 < 70 → left
Found at node 60
| Operation | Best/Average | Worst |
|---|---|---|
| Insertion | O(log n) | O(n) |
| Search | O(log n) | O(n) |
Worst case happens when the BST becomes skewed.
Fast searching in average case
Maintains ordered data
Useful for dynamic data
Can become skewed
Performance drops to O(n) in worst case
AVL trees are part of your unit coverage and are listed along with BST and heap topics in the course outline.
An AVL tree is a self-balancing binary search tree.
For every node, the height difference between left and right subtree is at most 1.
BF = Height(Left Subtree) - Height(Right Subtree)
-1, 0, +1
If balance factor goes beyond this range, rotations are used.
There are four types of rotations.
Used when insertion occurs in the left subtree of the left child.
Before:
After right rotation:
Used when insertion occurs in the right subtree of the right child.
Before:
After left rotation:
Used when insertion occurs in the right subtree of the left child.
Before:
Steps:
Left rotate 10
Right rotate 30
After:
Used when insertion occurs in the left subtree of the right child.
Before:
Steps:
Right rotate 30
Left rotate 10
After:
| Case | Rotation |
|---|---|
| LL | Right Rotation |
| RR | Left Rotation |
| LR | Left then Right |
| RL | Right then Left |
Strictly balanced
Fast searching
Height always O(log n)
Heap-related topics are part of your syllabus and unit outline, including minimum heap construction and heap data structure.
A heap is a complete binary tree that satisfies the heap property.
Two types:
1. Min Heap
2. Max Heap
In a min heap, parent node is smaller than or equal to its children.
Root is the smallest element.
In a max heap, parent node is greater than or equal to its children.
Root is the largest element.
1. Insert the new element at the last position.
2. Compare it with parent.
3. Swap if heap property is violated.
4. Repeat until property is satisfied.
Insert 15 into:
Insert at last:
Since 15 > 10, no swap needed.
If inserted value were smaller than parent, swap upward.
Deletion usually removes the root node.
1. Remove root.
2. Replace it with last element.
3. Heapify down.
4. Restore heap property.
Min Heap:
Delete 10:
Replace root with 50
Heapify down
After heapify:
| Operation | Time |
|---|---|
| Insert | O(log n) |
| Delete root | O(log n) |
| Get min/max | O(1) |
BST and AVL tree are both covered in your notes, and AVL is specifically described as a height-balanced binary tree while BST is the ordered binary search structure.
| Feature | BST | AVL Tree |
|---|---|---|
| Balance | May be unbalanced | Always balanced |
| Height | Can become O(n) | Always O(log n) |
| Search | Slower in worst case | Faster and reliable |
| Rotations | Not used | Required |
| Complexity | Average O(log n), worst O(n) | O(log n) for search/insert/delete |
| Implementation | Simpler | More complex |
BST is easy to implement but can become skewed.
AVL tree maintains balance using rotations, so performance stays efficient.
Your notes mention applications of trees and BSTs, including file systems, databases, routing, AI, syntax parsing, searching, and priority queues.
1. File Systems
Trees are used to represent folders and subfolders.
2. Databases
Trees help in indexing and fast searching.
3. Expression Evaluation
Expression trees are used to represent arithmetic expressions.
4. Syntax Parsing
Compilers use trees to analyze syntax.
5. Artificial Intelligence
Decision trees are used in AI and machine learning.
6. Network Routing
Trees help model routing structures.
1. Priority Queue
Heap is used to implement priority queues efficiently.
2. Heap Sort
Heap sort uses heap structure to sort data.
3. Scheduling
Operating systems use heaps for job and process scheduling.
4. Graph Algorithms
Heaps are used in algorithms like Dijkstra and Prim for efficient minimum selection.
5. Event Simulation
Heaps help process events based on priority or time.
| Data Structure | Main Use |
|---|---|
| Tree | Hierarchical representation |
| BST | Fast ordered searching |
| AVL Tree | Balanced searching |
| Heap | Priority-based access |
0 Comments