Tree and Binary Tree
A tree is a hierarchical data structure with branches, leaves, and nodes that are interconnected, resembling an inverted tree. It is called a "tree," but unlike a real tree, it is represented upside-down.
Example of Tree
In this image, you can see an upside-down tree structure with a root, branches, and leaves. These are all interconnected. The tree structure can become quite complex, so i explore binary tree first, which are simpler, and then you can try to implementing trees yourself 🙃.
Binary Tree
A binary tree is a simplified version of a tree. It has one root and a maximum of two child nodes: a left node and a right node. The left node stores values smaller than the root, and the right node stores values greater than the root. For example, if the root is 2, the left node might store 1, and the right node might store 3.
Example of Binary Tree
In the image above, you can see an example of a binary tree. The root is 2, with the left node storing 1 (smaller value) and the right node storing 3 (larger value). The left and right nodes can also become roots for their child nodes, continuing the hierarchy. This recursive structure makes binary trees very versatile.
Binary Tree Code
The code snippet demonstrates how to add values to a binary tree and print them. Initially, a tree object is created, and values such as 2, 1, and 3 are added. This example aligns with the binary tree shown earlier. If you were to add values in the order 1, 2, 3, the tree would grow linearly to the right, which isn't ideal for a binary tree. Let's break down the implementation step by step.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
// Constructor
Node(int v) : data(v), left(nullptr), right(nullptr) {}
};
At the top, i include the necessary headers and use the `std` namespace. The `Node` structure represents a single node in the tree, containing data, and pointers to its left and right child nodes. The constructor initializes the node with a value and sets both child pointers to `nullptr`.
struct Tree {
Node* root;
Tree() : root(nullptr) {}
The `Tree` structure contains the root of the binary tree, which is initialized to `nullptr` in the constructor.
// Add function
void add(int v) {
Node* n = new Node(v);
if (root == nullptr) {
root = n;
} else {
Node* t = root;
while (true) {
// If value is less than the current node's data
if (v < t->data) {
// If the left child is empty, add the node there
if (t->left == nullptr) {
t->left = n;
break;
} else {
// Otherwise, move to the left child
t = t->left;
}
}
The `add` function inserts a value into the binary tree. If the tree is empty, the new node becomes the root. Otherwise, the function compares the value to the current node's data and decides whether to traverse to the left or right subtree. For values less than the current node, it checks if the left child is empty and adds the node there, or continues traversing left.
// If value is greater than the current node's data
if (v > t->data) {
// If the right child is empty, add the node there
if (t->right == nullptr) {
t->right = n;
break;
} else {
// Otherwise, move to the right child
t = t->right;
}
}
}
}
}
};
For values greater than the current node, the function checks the right child and follows the same logic as the left child. This ensures the binary tree remains sorted, with smaller values on the left and larger values on the right.
This concludes today’s tutorial. See you in the next one 😊
Check out the full video tutorial:
