Non-Linear Data Structures & Basics

Trees are non-linear; data branches out instead of sitting in a sequence, drastically speeding up searches.
A tree contains a root node, and remaining nodes partition into disjoint sets (subtrees).

Terminology & Properties

Leaf nodes have no successors. Level = distance from root. Height = total levels. Depth = edges from root.
Binary trees have utmost 2 children. Nodes at level 'L' = 2^L. Total edges 'e' = n - 1.

1.0.0 Array Implementation Theory

0-Indexed Rule: Left child is at 2k+1. Right child is at 2k+2. Parent is at (k-1)/2.
Array representation saves space (no pointers) but is terrible for skewed trees due to massive memory wastage.

2.0.0 Includes & Globals

// Implementation of tree using array
// numbering starting from 0 to n-1.
#include<bits/stdc++.h>
using namespace std;

char tree[10];

2.0.1 Root Init

int root(char key) {
if (tree[0] != '\0')
cout << "Tree already had root";
else
tree[0] = key;
return 0;
}

2.0.2 Set Left Child

int set_left(char key, int parent) {
if (tree[parent] == '\0')
cout << "\nCan't set child at " << (parent * 2) + 1 << ", no parent found";
else
tree[(parent * 2) + 1] = key;
return 0;
}

2.0.3 Set Right Child

int set_right(char key, int parent) {
if (tree[parent] == '\0')
cout << "\nCan't set child at " << (parent * 2) + 2 << ", no parent found";
else
tree[(parent * 2) + 2] = key;
return 0;
}

2.0.4 Main Driver

// Driver Code
int main() {
root('A');
set_left('B',0);
set_right('C', 0);
set_left('D', 1);
set_right('E', 1);
set_right('F', 2);
print_tree();
return 0;
}

2.0.5 Full Code

// Implementation of tree using array
// numbering starting from 0 to n-1.
#include<bits/stdc++.h>
using namespace std;
char tree[10];

int root(char key) {
if (tree[0] != '\0')
cout << "Tree already had root";
else
tree[0] = key;
return 0;
}

int set_left(char key, int parent) {
if (tree[parent] == '\0')
cout << "\nCan't set child at " << (parent * 2) + 1 << ", no parent found";
else
tree[(parent * 2) + 1] = key;
return 0;
}

int set_right(char key, int parent) {
if (tree[parent] == '\0')
cout << "\nCan't set child at " << (parent * 2) + 2 << ", no parent found";
else
tree[(parent * 2) + 2] = key;
return 0;
}

// Driver Code
int main() {
root('A');
set_left('B',0);
set_right('C', 0);
set_left('D', 1);
set_right('E', 1);
set_right('F', 2);
print_tree();
return 0;
}

Logical Breakdown

Click the ➔ arrow on any line to reveal the underlying logic here.