Arrays

Introduction to Trees

A tree is a hierarchical data structure with a root node, and each node can have children. Used in: file systems, databases, BSTs, etc.

Key Properties

• Root: Top node
• Leaf: Node with no children
• Edge: Link between nodes
• Height: Root to deepest leaf
• Depth: Root to a node
• Binary Tree: Max 2 children
• BST: Left < Root < Right

Example in C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* newNode(int val) {
    return new Node{val, nullptr, nullptr};
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    Node* root = newNode(10);
    root->left = newNode(5);
    root->right = newNode(15);

    inorder(root);  // Output: 5 10 15
}

    

Learning resource

Readings Trees
Videos Trees