Introduction to Tree Data Structure
A tree is a hierarchical data structure used to organize and represent data in a parent–child
relationship.
It consists of nodes, where the topmost node is called the root, and every other node can have
one or more child nodes.
nodes.
Basic Terminologies In Tree Data Structure:
● Parent Node: A node that is an immediate predecessor of another node. Example: 35 is
the parent of 3 and 6.
● Child Node: A node that is an immediate successor of another node. Example: 3 and 6 are
children of 35.
● Root Node: The topmost node in a tree, which does not have a parent. Example: 15 is the
root node.
● Leaf Node (External Node): Nodes that do not have any children. Example: 1, 10, 12, 5, 7, 7
are leaf nodes.
● Ancestor: Any node on the path from the root to a given node (excluding the node itself).
Example: 15 and 35 are ancestors of 10.
● Descendant: A node x is a descendant of another node y if y is an ancestor of x. Example:
1, 10, and 6 are descendants of 35.
● Sibling: Nodes that share the same parent. Example: 1 and 10 are siblings, and 5 and 7 are
siblings.
● Level of a Node: The number of edges in the path from the root to that [Link] root
node is at level 0.
● Internal Node: A node with at least one child.
● Neighbor of a Node: The parent or children of a node.
● Subtree: A node and all its descendants form a subtree.
Why Tree is considered a non-linear data structure?
Data in a tree is not stored sequentially (i.e., not in a linear order). Instead, it is organized across
multiple levels, forming a hierarchical structure. Because of this arrangement, a tree is classified
as a non-linear data structure.
Representation of a Node in Tree Data Structure:
A tree can be represented using a collection of nodes. Each of the nodes can be represented
with the help of class or structs.
// Node structure for tree
class Node {
public:
int data;
vector<Node*> children;
Node(int x) {
data = x;
}
};
Importance of Tree Data Structure:
● Trees are useful for storing data that naturally forms a hierarchy.
● File systems on computers are structured as trees, with folders containing subfolders and
files.
● The DOM (Document Object Model) of an HTML page is a tree:The <html> tag is the
root.<head> and <body> are its [Link] tags can have their own child nodes,
forming a hierarchical structure.
● Trees help in efficient data organization and retrieval for hierarchical relationships.
Types of Trees
A tree is a hierarchical data structure that consists of nodes connected by edges. It is used to
represent relationships between elements, where each node holds data and is connected to
other nodes with edges.
1. Binary Tree
A binary tree is a tree data structure where each node has at most two children. These two
children are usually referred to as the left child and right child.
Example: Consider the tree below. Since each node of this tree has at most 2 children, it can be
said that this tree is a Binary tree.
Types of Binary Tree:
● Binary Search Tree (BST) and its Variations: A BST is a binary tree where each node has
at most two children, and for each node, the left child’s value is smaller than the node’s
value, and the right child’s value is greater.
● Binary Indexed Tree: A data structure that uses a binary tree to efficiently compute and
update prefix sums in an array.
● Balanced Binary Tree: A binary tree where the difference in heights between the left and
right subtrees of any node is minimal (often defined as at most 1). Examples of Balanced
Binary Tree are AVL Tree.
Binary Search Tree
A Binary Search Tree (BST) is a type of binary tree data structure in which each node contains a
unique key and satisfies a specific ordering property:
● All nodes in the left subtree of a node contain values strictly less than the node’s value.
● All nodes in the right subtree of a node contain values strictly greater than the node’s
●
value.
This structure enables efficient operations for searching, insertion, and deletion of elements,
especially when the tree remains balanced.
● BSTs are widely used in database indexing, symbol tables, range queries, and are
foundational for advanced structures like AVL Trees.
● In problem solving, BSTs are used in problems where we need to maintain sorted stream of
data.
● Operations like search, insertion, and deletion work in O(Log n) time for a balanced binary
search tree. In the worst-case (unbalanced), these degrade to O(n). With self-balancing
BSTs like AVL and Red Black Trees, we can ensure the worst case as O(Log n).
Insertion in Binary Search Tree (BST)
Given the root of a Binary Search Tree, we need to insert a new node with given value in the BST.
All the nodes have distinct values in the BST and we may assume that the the new value to be
inserted is not present in BST.
Example:
A new key is inserted at the position that maintains the BST property. We start from the root and
move downward: if the key is smaller, go left; if larger, go right. We continue until we find an
unoccupied spot where the node can be placed without violating the BST property, and insert it
there as a new leaf.
leaf.
Insertion in Binary Search Tree using Recursion:
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
// Node structure
class Node {
public:
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = right = nullptr;
}
};
int getHeight(Node* root, int h) {
if (root == nullptr) return h - 1;
return max(getHeight(root->left, h + 1),
getHeight(root->right, h + 1));
}
void levelOrder(Node* root) {
queue<pair<Node*, int>> q;
[Link]({root, 0});
int lastLevel = 0;
int height = getHeight(root, 0);
while (![Link]()) {
auto top = q×front();
[Link]();
Node* node = [Link];
int lvl = top×second;
if (lvl > lastLevel) {
cout << "
";
lastLevel = lvl;
}
// all levels are printed
if (lvl > height) break;
// printing null node
cout << (node->data == -1 ? "N" : to_string(node-
>data)) << " ";
// null node has no children
if (node->data == -1) continue;
if (node->left == nullptr) [Link]({new Node(-1),
lvl + 1});
else [Link]({node->left, lvl + 1});
if (node->right == nullptr) [Link]({new Node(-1),
lvl + 1});
else [Link]({node->right, lvl + 1});
}
}
Node* insert(Node* root, int key) {
// If the tree is empty, return a new node
if (root == nullptr)
return new Node(key);
// Otherwise, recur down the tree
if (key < root->data)
root->left = insert(root->left, key);
else
root->right = insert(root->right, key);
// Return the (unchanged) node pointer
return root;
}
int main() {
Node* root = nullptr;
// Create BST
// 22
// / \
// 12 30
// / \
// 8 20
// / \
// 15 30
root = insert(root, 22);
root = insert(root, 12);
root = insert(root, 30);
root = insert(root, 8);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 15);
// print the level order
// traversal of the BST
levelOrder(root);
}
Output
22
12 30
8 20 N 30
N N 15 N N N
Time Complexity: O(h)
● The worst-case time complexity of insert operations is O(h) where h is the height of the
Binary Search Tree.
● In the worst case, we may have to travel from the root to the deepest leaf node. The height
of a skewed tree may become n and the time complexity of insertion operation may
becomeO(n).
Auxiliary Space: O(h), due to recursive stack.
Insertion in Binary Search Tree using Iterative approach:
Instead of using recursion, we can also implement the insertion operation iteratively using a
while loop. Below is the implementation using a while loop, using the same idea as above.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
// Node structure
class Node {
public:
int data;
Node* left;
Node* right;
Node(int item) {
data = item;
left = right = nullptr;
}
};
int getHeight(Node* root, int h) {
if (root == nullptr) return h - 1;
return max(getHeight(root->left, h + 1),
getHeight(root->right, h + 1));
}
void levelOrder(Node* root) {
queue<pair<Node*, int>> queue;
[Link]({root, 0});
int lastLevel = 0;
int height = getHeight(root, 0);
while (![Link]()) {
auto top = queue×front();
[Link]();
Node* node = [Link];
int lvl = top×second;
if (lvl > lastLevel) {
cout << "
";
lastLevel = lvl;
}
// all levels are printed
if (lvl > height) break;
// printing null node
cout << (node->data == -1 ? "N" : to_string(node-
>data)) << " ";
// null node has no children
if (node->data == -1) continue;
if (node->left == nullptr) [Link]({new
Node(-1), lvl + 1});
else [Link]({node->left, lvl + 1});
if (node->right == nullptr) [Link]({new
Node(-1), lvl + 1});
else [Link]({node->right, lvl + 1});
}
}
Node* insert(Node* root, int key) {
Node* temp = new Node(key);
// If tree is empty
if (root == nullptr) {
return temp;
}
// Find the node who is going to
// have the new node as its child
Node* curr = root;
while (curr != nullptr) {
if (curr->data > key && curr->left != nullptr) {
curr = curr->left;
} else if (curr->data < key && curr->right !=
nullptr) {
curr = curr->right;
} else break;
}
// If key is smaller, make it left
// child, else right child
if (curr->data > key) {
curr->left = temp;
} else {
curr->right = temp;
}
return root;
}
int main() {
Node× root = nullptr;
// Create BST
// 22
// / \
// 12 30
// / \
// 8 20
// / \
// 15 30
root = insert(root, 22);
root = insert(root, 12);
root = insert(root, 30);
root = insert(root, 8);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 15);
// print the level order traversal of the BST
levelOrder(root);
}
Output
22
12 30
8 20 N 30
N N 15 N N N
Time complexity: O(h), where h is the height of the tree.
Auxiliary space: O(1)
Searching in Binary Search Tree (BST)
Given the root of a Binary Search Tree and a value key, find if key is present in the BST or not.
Note: The key may or may not be present in the BST.
Input: key = 7
Output: true
Explanation: 7 is present in the BST.
Input: key = 14
Output: false
Explanation: 14 is not present in the BST.
How to search a value in Binary Search Tree:
Let's say we want to search for the number key, We start at the root. Then:
● We compare the value to be searched with the value of the root.
● If it's equal we are done with the search.
● If it's smaller we know that we need to go to the left subtree.
● If it's greater we search in the right subtree.
● Repeat the above step till no more traversal is possible
● If at any iteration, key is found, return True. If the node is null, return False.
Example of searching a key in BST:
Searching in Binary Search Tree using Recursion:
#include <iostream>
using namespace std;
// Node structure
class Node {
public:
int data;
Node* left;
Node* right;
Node(int item) {
data = item;
left = right = nullptr;
}
};
bool search(Node* root, int key) {
// root is null -> return false
if (root == nullptr) return false;
// if root has key -> return true
if (root->data == key) return true;
if (key > root->data)
return search(root->right, key);
else
return search(root->left, key);
}
int main() {
// Creating BST
// 6
// / \
// 2 8
// / \
// 7 9
Node× root = new Node(6);
root->left = new Node(2);
root->right = new Node(8);
root->right->left = new Node(7);
root->right->right = new Node(9);
int key = 7;
// Searching for key in BST
cout << search(root, key) << endl;
}
Output
1
Time complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(h) This is because of the space needed to store the recursion stack.
We can avoid the auxiliary space and recursion overhead withe help of iterative implementation.
Below is the iterative implementation that works in O(h) time and O(1) auxiliary space.
Searching in Binary Search Tree using Iterative approach:
#include <iostream>
using namespace std;
// Node structure
class Node {
public:
int data;
Node* left;
Node* right;
Node(int item) {
data = item;
left = right = nullptr;
}
};
bool search(Node* root, int key) {
bool present = false;
// iterative traversal
while (root != nullptr) {
if (root->data == key) {
present = true;
break;
}
else if (key > root->data)
root = root->right;
else
root = root->left;
}
return present;
}
int main() {
// Creating BST
// 6
// / \
// 2 8
// / \
// 7 9
Node× root = new Node(6);
root->left = new Node(2);
root->right = new Node(8);
root->right->left = new Node(7);
root->right->right = new Node(9);
int key = 7;
// Searching for key in BST
cout << search(root, key) << endl;
}
Output
1
Time complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(1)
Deletion in Binary Search Tree (BST)
Given the root of a Binary Search Tree (BST) and an integer x, delete the node with value x from
the BST while maintaining the BST property.
Input: x = 15
Output: [[10], [5, 18], [N, N, 12, N]]
Explanation: The node with value x (15) is deleted from BST.
Deleting a node in a BST means removing the target node while ensuring that the tree remains a
valid BST. Depending on the structure of the node to be deleted, there are three possible
scenarios:
Case 1: Node has No Children (Leaf Node)
If the target node is a leaf node, it can be directly removed from the tree since it has no child to
maintain.
Working:
Case 2: Node has One Child(Left or Right Child)
If the target node has only one child, we remove the node and connect its parent directly to its
only child. This way, the tree remains valid after deletion of target node.
Working:
Case 3: Node has Two Children
If the target node has two children, deletion is slightly more complex.
To maintain the BST property, we need to find a replacement node for the target. The
replacement can be either:
● The inorder successor — the smallest value in the right subtree, which is the next greater
value than the target node.
● The inorder predecessor — the largest value in the left subtree, which is the next smaller
value than the target node.
Once the replacement node is chosen, we replace the target node’s value with that node’s value,
and then delete the replacement node, which will now fall under Case 1 (no children) or Case 2
(one child).
Note: Inorder predecessor can also be used.
Working:
The deletion process in BST depends on the number of children of the node.
● No children means simply remove the node.
● One child means remove the node and connect its parent to the node’s only child.
● Two children means replace the node with its inorder successor/predecessor and delete
that node.
This ensures that the BST property remains intact after every deletion.
#include <iostream>
#include<vector>
#include<unordered_map>
#include <queue>
using namespace std;
// Node structure
class Node {
public:
int data;
Node* left;
Node* right;
Node(int x) {
data = x;
left = right = nullptr;
}
};
// Calculate Height
int getHeight(Node* root, int h) {
if (root == nullptr) return h - 1;
return max(getHeight(root->left, h + 1),
getHeight(root->right, h + 1));
}
// Print Level Order
void levelOrder(Node* root) {
queue<pair<Node*, int>> q;
[Link]({root, 0});
int lastLevel = 0;
// function to get the height of tree
int height = getHeight(root, 0);
// printing the level order of tree
while (![Link]()) {
auto top = q×front(); [Link]();
Node* node = [Link];
int lvl = top×second;
if (lvl > lastLevel) {
cout << "
";
lastLevel = lvl;
}
// all levels are printed
if (lvl > height) break;
if (node->data != -1) cout << node->data << " ";
// printing null node
else cout << "N ";
// null node has no children
if (node->data == -1) continue;
if (node->left == nullptr) [Link]({new Node(-1),
lvl + 1});
else [Link]({node->left, lvl + 1});
if (node->right == nullptr) [Link]({new Node(-1),
lvl + 1});
else [Link]({node->right, lvl + 1});
}
}
// Get inorder successor (smallest in right subtree)
Node* getSuccessor(Node* curr) {
curr = curr->right;
while (curr != nullptr && curr->left != nullptr)
curr = curr->left;
return curr;
}
// Delete a node with value x from BST
Node* delNode(Node* root, int x) {
if (root == nullptr)
return root;
if (root->data > x)
root->left = delNode(root->left, x);
else if (root->data < x)
root->right = delNode(root->right, x);
else {
// Node with 0 or 1 child
if (root->left == nullptr) {
Node* temp = root->right;
delete root;
return temp;
}
if (root->right == nullptr) {
Node* temp = root->left;
delete root;
return temp;
}
// Node with 2 children
Node* succ = getSuccessor(root);
root->data = succ->data;
root->right = delNode(root->right, succ->data);
}
return root;
}
int main() {
Node× root = new Node(10);
root->left = new Node(5);
root->right = new Node(15);
root->right->left = new Node(12);
root->right->right = new Node(18);
int x = 15;
root = delNode(root, x);
levelOrder(root);
return 0;
}
Output
10
5 18
N N 12 N
Time Complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(h).
AVL Tree Data Structure
An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between
heights of left and right subtrees for any node cannot be more than one.
Balance Factor = left subtree height - right subtree height
For a Balanced Tree(for every node): -1 ≤ Balance Factor ≤ 1
Example of an AVL Tree:
The balance factors for different nodes are: 12 : +1, 8 : +1, 18 : +1, 5 : +1, 11 : 0, 17 : 0 and 4 : 0.
Since all differences are lies between -1 to +1, so the tree is an AVL tree.
Example of a BST which is not an AVL Tree:
The Below Tree is not an AVL Tree as the balance factor for nodes 8 and 12 is more than 1.
Important Points about AVL Tree:
● Rotations: rotations are designed to restore balance in O(1) time while ensuring the overall
time complexity remains O(log n). AVL Trees use four cases to rebalance themselves after
insertions and deletions: Left-Left (LL), Right-Right (RR), Left-Right (LR) and Right-Left
(RL)
● Insertion and Deletion: While insertion is followed by upward traversals to check balance
and apply rotations, deletion can be more complex due to multiple rotations possibly being
required. AVL Trees may require multiple rebalancing steps during deletion, unlike Red-
Black Trees which limit this better.
● Use Cases: AVL Trees are particularly useful when you need frequent and efficient
lookups, like in database indexing, memory-intensive applications, or where predictable
time complexity is crucial.
● Drawbacks Compared to Other Trees: Although faster in lookups than Red-Black Trees,
AVL Trees might incur slightly more overhead on insertions and deletions due to stricter
balancing requirements. As a result, Red-Black Trees are more common in standard
libraries like TreeMap or TreeSet in Java or map in C++ STL.
● In-order Traversal: An in-order traversal of an AVL Tree still gives you elements in sorted
order, just like any Binary Search Tree.
Operations on an AVL Tree:
● Searching : It is same as normal Binary Search Tree (BST) as an AVL Tree is always a BST.
So we can use the same implementation as BST. The advantage here is time complexity is
O(log n)
● Insertion : It does rotations along with normal BST insertion to make sure that the balance
factor of the impacted nodes is less than or equal to 1 after insertion
● Deletion : It also does rotations along with normal BST deletion to make sure that the
balance factor of the impacted nodes is less than or equal to 1 after deletion.
Rotating the subtrees (Used in Insertion and Deletion)
An AVL tree may rotate in one of the following four ways to keep itself balanced while making
sure that the BST properties are maintained.
1. Left-Left Case:
● Occurs when a node is inserted into the left subtree of the left child, causing the balance
factor to become more than +1.
● Fix: Perform a single right rotation.
2. Right-Right Case:
● Occurs when a node is inserted into the right subtree of the right child, making the
balance factor less than -1.
● Fix: Perform a single left rotation.
Left-Right Case:
● Occurs when a node is inserted into the right subtree of the left child, which disturbs the
balance factor of an ancestor node, making it left-heavy.
● Fix: Perform a left rotation on the left child, followed by a right rotation on the node.
Right-Left Case:
● Occurs when a node is inserted into the left subtree of the right child, which disturbs the
balance factor of an ancestor node, making it right-heavy.
● Fix: Perform a right rotation on the right child, followed by a left rotation on the node.
Applications of AVL Tree:
. AVL Tree is used as a first example self balancing BST in teaching DSA as it is easier to
understand and implement compared to Red Black
. Applications, where insertions and deletions are less common but frequent data lookups
along with other operations of BST like sorted traversal, floor, ceil, min and max.
. AVL Trees can be used in a real time environment where predictable and consistent
performance is required.
Advantages of AVL Tree:
. AVL trees can self-balance themselves and therefore provides time complexity as O(log n)
for search, insert and delete.
. As it is a balanced BST, so items can be traversed in sorted order.
. Since the balancing rules are strict, AVL trees in general have relatively less height and
hence the search is faster.
. AVL tree is relatively less complex to understand and implement compared to Red Black
Trees.
Disadvantages of AVL Tree:
. It is difficult to implement compared to normal BST.
. Less used compared to Red-Black trees. Due to its rather strict balance.
. AVL trees provide complicated insertion and removal operations as more rotations are
performed.