A tree is a hierarchical non-linear data structure consisting of nodes connected by edges. It starts with a root node and branches out into child nodes, forming parent-child relationships. Each node can have zero or more children, but only one parent (except the root, which has no parent).
Trees are widely used for representing hierarchical data such as file systems, organizational structures, and XML/HTML documents. Operations like insertion, deletion, and search depend on the specific type of tree, but generally provide efficient O(log n) to O(n)time complexity.
Step 1: Create a root node by entering a value and clicking "Create Root".
Step 2: Click on any node to select it (it will turn blue).
Step 3: Enter a value and click "Add to Selected Node" to add a child to the selected node.
Step 4: Continue adding children to build your tree structure.
Note: Click on any node to select it as the parent for the next child node.
Root: The topmost node with no parent.
Parent: A node that has one or more children.
Child: A node that has a parent.
Leaf: A node with no children (terminal node).
Subtree: A tree formed by a node and all its descendants.
Depth: The distance from the root to a specific node.
Height: The distance from a node to the deepest leaf in its subtree.
Insert: Add a new node as a child of a specified parent node.
Delete: Remove a node and handle its children (reattach or remove subtree).
Search/Find: Locate a node with a specific value using traversal.
Traversal: Visit all nodes in a specific order (preorder, inorder, postorder, level-order).
Height: Calculate the maximum depth from root to any leaf.
Count: Count total nodes, leaf nodes, or internal nodes.
DFS Traversals: Preorder (root-left-right), Inorder (left-root-right), Postorder (left-right-root) for different use cases.
BFS/Level Order: Use queue to process nodes level by level; useful for level-wise operations.
Tree Height/Depth: Recursively find max of left and right subtree heights plus one.
Lowest Common Ancestor: Find the deepest node that is ancestor of two given nodes.
Path Problems: Track path from root to node, find all paths, or path with specific sum.
Serialize/Deserialize: Convert tree to string representation and reconstruct it.
Mirror/Invert Tree: Swap left and right children recursively for all nodes.
/* General Tree implementation in C */
#include <stdio.h>
#include <stdlib.h>
#define MAX_CHILDREN 10
typedef struct TreeNode {
int value;
struct TreeNode* children[MAX_CHILDREN];
int childCount;
} TreeNode;
/* Create a new node */
TreeNode* createNode(int value) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->value = value;
node->childCount = 0;
for (int i = 0; i < MAX_CHILDREN; i++) {
node->children[i] = NULL;
}
return node;
}
/* Add child to a parent node */
void addChild(TreeNode* parent, TreeNode* child) {
if (parent->childCount < MAX_CHILDREN) {
parent->children[parent->childCount++] = child;
}
}
/* Pre-order traversal */
void preOrder(TreeNode* node) {
if (node == NULL) return;
printf("%d ", node->value);
for (int i = 0; i < node->childCount; i++) {
preOrder(node->children[i]);
}
}
int main() {
TreeNode* root = createNode(1);
TreeNode* child1 = createNode(2);
TreeNode* child2 = createNode(3);
addChild(root, child1);
addChild(root, child2);
addChild(child1, createNode(4));
preOrder(root); // Output: 1 2 4 3
return 0;
}