Video Explanation:

Types of Trees	Description
Binary Tree	A tree where each node has at most 2 children.
Binary Search Tree (BST)	A binary tree where all values in the left subtree are less than the node, and all values in the right subtree are greater than the node.
Self-Balancing Binary Search Tree	A BST that automatically keeps its height controlled to make search, insert, and delete efficient, such as AVL trees and Red-Black trees.
Binary Heap	A complete binary tree where every parent follows a min-heap or max-heap ordering rule.
String Trees	Trees specialized for storing and searching strings, prefixes, or suffixes.
Trie (Prefix Tree)	A tree-like structure used to store strings efficiently, especially for prefix search.
Suffix Tree	A compressed tree-like structure used for efficient substring and pattern matching.
Multiway Search Tree	A search tree where each node can have multiple children and can organize many keys efficiently.
B-tree / B+ Tree	Self-balancing multiway search trees commonly used in databases and file systems for indexing.
Array-Based Query Trees	Tree-like structures usually stored in arrays and used for efficient range queries and updates.
Binary Indexed Tree (Fenwick Tree)	An array-based tree-like structure used for prefix sum queries and point updates.
Segment Tree	An array-based or node-based tree structure used for range queries such as sum, min, max, and gcd.

Tree

What Is a Tree 🌳 ?

A Tree is a non-linear, hierarchical data structure composed of nodes. In graph theory, a tree is an undirected, connected, acyclic graph. In data structures, we usually work with a rooted tree, where one node is chosen as the root.

The topmost node is called the root.

Each node can have zero or more children, but each non-root node has exactly one parent.

There are no cycles, ensuring a clear parent-child relationship.

In an undirected tree, there is exactly one path between any two nodes

A tree with N nodes has exactly N - 1 edges.

Trees are used to represent hierarchies, structured data, and recursive relationships.

Every tree is a graph, but not every graph is a tree.

Concept Tree Graph

Preorder/Postorder ✅ Sometimes

DFS / BFS Traversal ✅ ✅

Can have cycles ❌ ✅

Parent-child structure ✅ Sometimes

Basic Terminology

Term	Description
Root	Root The top node of a rooted tree
Node	A unit containing data and links to other nodes
Edge	Connection between two nodes
Parent	Node that has children
Child	Node connected below another node
Leaf	Node with no children
Subtree	Any node with its descendants
Depth	Depth Number of edges from the root to a node
Height	Height Number of edges on the longest path from a node to a leaf
Level	Depth + 1, if the root starts at level 1
Sibling	Nodes that share the same parent

Real-Life Use Cases

Use Case	Application
File System	Directories are modeled as trees
Web Pages	HTML DOM tree
AI / Games	Decision trees, minimax
Compilers	Abstract Syntax Tree (AST)
Auto-complete	Tries for efficient prefix search
Databases	B-trees / B+ trees for indexing
Networks	Networks Spanning trees are used to avoid cycles in network topologies.

Tree Types

Binary Tree
N-ary Tree
Specialized Trees

Binary Tree

A Binary Tree is a special type of tree data structure where:

Each node has at most two children.

The children are referred to as the left child and the right child.

Each node typically contains:
- A value
- A reference to the left child
- A reference to the right child

Binary Tree Types

Type	Description
Full Binary Tree	Every node has 0 or 2 children
Perfect Binary Tree	All internal nodes have 2 children and all leaves are at the same level
Complete Binary Tree	All levels are filled except possibly the last; filled left to right
Balanced Binary Tree	Heights of subtrees differ by at most 1
Degenerate Tree	Each node has only one child → like a linked list
Binary Search Tree (BST)	Left child < Node < Right child

Traversal

1. Depth-First Traversal

2. Breadth-First Traversal

// Node Structure-Binary trees
class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

        50
       /  \
     30    70
    / \    / \
   20 40  60 80

1. Depth-First Traversal

Video: Learn Tree traversal in 3 minutes 🧗

Binary Tree Traversal Type	Order	Description
Preorder	Node → Left → Right	Visit the node first, then recursively traverse the left and right subtrees.
Inorder	Left → Node → Right	Traverse the left subtree, then visit the node, then the right subtree.
Postorder	Left → Right → Node	Visit children first, then the node.

Order	Visit Sequence	Example Use Case	Result
Preorder	Root → Left → Right	Copying a tree	[50, 30, 20, 40, 70, 60, 80]
Inorder	Left → Root → Right	Retrieving sorted data from a BST	[20, 30, 40, 50, 60, 70, 80]
Postorder	Left → Right → Root	Deleting a tree	[20, 40, 30, 60, 80, 70, 50]

2. Breadth-First Traversal

Visits all nodes at the current depth level before moving down.

Level Order (levelOrder) → level by level (left to right), uses a queue. // [50, 30, 70, 20, 40, 60, 80]
- Level 0: 50
- Level 1: 30, 70
- Level 2: 20, 40, 60, 80

Implementation

class BinaryTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinaryTree {
  constructor(root = null) {
    this.root = root;
  }

  preOrder() {
    const result = [];
    this.preOrderHelper(this.root, result);
    return result;
  }

  preOrderHelper(node, result) {
    if (!node) return;

    result.push(node.value);
    this.preOrderHelper(node.left, result);
    this.preOrderHelper(node.right, result);
  }

  inOrder() {
    const result = [];
    this.inOrderHelper(this.root, result);
    return result;
  }

  inOrderHelper(node, result) {
    if (!node) return;

    this.inOrderHelper(node.left, result);
    result.push(node.value);
    this.inOrderHelper(node.right, result);
  }

  postOrder() {
    const result = [];
    this.postOrderHelper(this.root, result);
    return result;
  }

  postOrderHelper(node, result) {
    if (!node) return;

    this.postOrderHelper(node.left, result);
    this.postOrderHelper(node.right, result);
    result.push(node.value);
  }

  levelOrder() {
    if (!this.root) return [];

    const queue = [this.root];
    const result = [];
    let front = 0;

    while (front < queue.length) {
      const node = queue[front];
      front++;

      result.push(node.value);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    return result;
  }
}

from collections import deque
from typing import Any, Optional


class BinaryTreeNode:
    def __init__(self, value: Any):
        self.value = value
        self.left: Optional["BinaryTreeNode"] = None
        self.right: Optional["BinaryTreeNode"] = None


class BinaryTree:
    def __init__(self, root: Optional[BinaryTreeNode] = None):
        self.root = root

    def pre_order(self) -> list[Any]:
        result: list[Any] = []
        self._pre_order_helper(self.root, result)
        return result

    def _pre_order_helper(self, node: Optional[BinaryTreeNode], result: list[Any]) -> None:
        if node is None:
            return

        result.append(node.value)
        self._pre_order_helper(node.left, result)
        self._pre_order_helper(node.right, result)

    def in_order(self) -> list[Any]:
        result: list[Any] = []
        self._in_order_helper(self.root, result)
        return result

    def _in_order_helper(self, node: Optional[BinaryTreeNode], result: list[Any]) -> None:
        if node is None:
            return

        self._in_order_helper(node.left, result)
        result.append(node.value)
        self._in_order_helper(node.right, result)

    def post_order(self) -> list[Any]:
        result: list[Any] = []
        self._post_order_helper(self.root, result)
        return result

    def _post_order_helper(self, node: Optional[BinaryTreeNode], result: list[Any]) -> None:
        if node is None:
            return

        self._post_order_helper(node.left, result)
        self._post_order_helper(node.right, result)
        result.append(node.value)

    def level_order(self) -> list[Any]:
        if self.root is None:
            return []

        queue: deque[BinaryTreeNode] = deque([self.root])
        result: list[Any] = []

        while queue:
            node = queue.popleft()
            result.append(node.value)

            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)

        return result

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class BinaryTreeNode<T> {
    T value;
    BinaryTreeNode<T> left;
    BinaryTreeNode<T> right;

    BinaryTreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree<T> {
    private BinaryTreeNode<T> root;

    public BinaryTree() {
        this.root = null;
    }

    public BinaryTree(BinaryTreeNode<T> root) {
        this.root = root;
    }

    public List<T> preOrder() {
        List<T> result = new ArrayList<>();
        preOrderHelper(root, result);
        return result;
    }

    private void preOrderHelper(BinaryTreeNode<T> node, List<T> result) {
        if (node == null) return;

        result.add(node.value);
        preOrderHelper(node.left, result);
        preOrderHelper(node.right, result);
    }

    public List<T> inOrder() {
        List<T> result = new ArrayList<>();
        inOrderHelper(root, result);
        return result;
    }

    private void inOrderHelper(BinaryTreeNode<T> node, List<T> result) {
        if (node == null) return;

        inOrderHelper(node.left, result);
        result.add(node.value);
        inOrderHelper(node.right, result);
    }

    public List<T> postOrder() {
        List<T> result = new ArrayList<>();
        postOrderHelper(root, result);
        return result;
    }

    private void postOrderHelper(BinaryTreeNode<T> node, List<T> result) {
        if (node == null) return;

        postOrderHelper(node.left, result);
        postOrderHelper(node.right, result);
        result.add(node.value);
    }

    public List<T> levelOrder() {
        List<T> result = new ArrayList<>();
        if (root == null) return result;

        Queue<BinaryTreeNode<T>> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            BinaryTreeNode<T> node = queue.remove();
            result.add(node.value);

            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }

        return result;
    }
}

#include<queue>
#include<vector>
using namespace std;

template <typename T>
class BinaryTreeNode {
public:
    T value;
    BinaryTreeNode<T>* left;
    BinaryTreeNode<T>* right;

    BinaryTreeNode(T value) {
        this->value = value;
        this->left = nullptr;
        this->right = nullptr;
    }
};

template <typename T>
class BinaryTree {
private:
    BinaryTreeNode<T>* root;

    void preOrderHelper(BinaryTreeNode<T>* node, vector<T>& result) {
        if (node == nullptr) return;

        result.push_back(node->value);
        preOrderHelper(node->left, result);
        preOrderHelper(node->right, result);
    }

    void inOrderHelper(BinaryTreeNode<T>* node, vector<T>& result) {
        if (node == nullptr) return;

        inOrderHelper(node->left, result);
        result.push_back(node->value);
        inOrderHelper(node->right, result);
    }

    void postOrderHelper(BinaryTreeNode<T>* node, vector<T>& result) {
        if (node == nullptr) return;

        postOrderHelper(node->left, result);
        postOrderHelper(node->right, result);
        result.push_back(node->value);
    }

public:
    BinaryTree(BinaryTreeNode<T>* root = nullptr) {
        this->root = root;
    }

    vector<T> preOrder() {
        vector<T> result;
        preOrderHelper(root, result);
        return result;
    }

    vector<T> inOrder() {
        vector<T> result;
        inOrderHelper(root, result);
        return result;
    }

    vector<T> postOrder() {
        vector<T> result;
        postOrderHelper(root, result);
        return result;
    }

    vector<T> levelOrder() {
        vector<T> result;
        if (root == nullptr) return result;

        queue<BinaryTreeNode<T>*> q;
        q.push(root);

        while (!q.empty()) {
            BinaryTreeNode<T>* node = q.front();
            q.pop();

            result.push_back(node->value);

            if (node->left != nullptr) q.push(node->left);
            if (node->right != nullptr) q.push(node->right);
        }

        return result;
    }
};

#include<stddef.h>
#include<stdlib.h>

typedef struct BinaryTreeNode {
    int value;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BinaryTreeNode;

typedef struct {
    int* data;
    int size;
    int capacity;
} IntArray;

BinaryTreeNode* createBinaryTreeNode(int value) {
    BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    if (node == NULL) return NULL;

    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void freeBinaryTree(BinaryTreeNode* root) {
    if (root == NULL) return;

    freeBinaryTree(root->left);
    freeBinaryTree(root->right);
    free(root);
}

IntArray createIntArray(int capacity) {
    IntArray array;
    array.data = (int*)malloc(sizeof(int) * capacity);
    array.size = 0;
    array.capacity = capacity;
    return array;
}

void appendInt(IntArray* array, int value) {
    if (array->size == array->capacity) {
        int newCapacity = array->capacity == 0 ? 1 : array->capacity * 2;
        int* newData = (int*)realloc(array->data, sizeof(int) * newCapacity);
        if (newData == NULL) return;

        array->data = newData;
        array->capacity = newCapacity;
    }

    array->data[array->size] = value;
    array->size++;
}

void freeIntArray(IntArray* array) {
    free(array->data);
    array->data = NULL;
    array->size = 0;
    array->capacity = 0;
}

void preOrderHelper(BinaryTreeNode* node, IntArray* result) {
    if (node == NULL) return;

    appendInt(result, node->value);
    preOrderHelper(node->left, result);
    preOrderHelper(node->right, result);
}

IntArray preOrder(BinaryTreeNode* root) {
    IntArray result = createIntArray(8);
    preOrderHelper(root, &result);
    return result;
}

void inOrderHelper(BinaryTreeNode* node, IntArray* result) {
    if (node == NULL) return;

    inOrderHelper(node->left, result);
    appendInt(result, node->value);
    inOrderHelper(node->right, result);
}

IntArray inOrder(BinaryTreeNode* root) {
    IntArray result = createIntArray(8);
    inOrderHelper(root, &result);
    return result;
}

void postOrderHelper(BinaryTreeNode* node, IntArray* result) {
    if (node == NULL) return;

    postOrderHelper(node->left, result);
    postOrderHelper(node->right, result);
    appendInt(result, node->value);
}

IntArray postOrder(BinaryTreeNode* root) {
    IntArray result = createIntArray(8);
    postOrderHelper(root, &result);
    return result;
}

IntArray levelOrder(BinaryTreeNode* root) {
    IntArray result = createIntArray(8);
    if (root == NULL) return result;

    int capacity = 8;
    int front = 0;
    int back = 0;
    BinaryTreeNode** queue = (BinaryTreeNode**)malloc(sizeof(BinaryTreeNode*) * capacity);
    if (queue == NULL) return result;

    queue[back++] = root;

    while (front < back) {
        BinaryTreeNode* node = queue[front++];
        appendInt(&result, node->value);

        if (node->left != NULL) {
            if (back == capacity) {
                capacity *= 2;
                BinaryTreeNode** newQueue = (BinaryTreeNode**)realloc(queue, sizeof(BinaryTreeNode*) * capacity);
                if (newQueue == NULL) break;
                queue = newQueue;
            }
            queue[back++] = node->left;
        }

        if (node->right != NULL) {
            if (back == capacity) {
                capacity *= 2;
                BinaryTreeNode** newQueue = (BinaryTreeNode**)realloc(queue, sizeof(BinaryTreeNode*) * capacity);
                if (newQueue == NULL) break;
                queue = newQueue;
            }
            queue[back++] = node->right;
        }
    }

    free(queue);
    return result;
}

class BinaryTreeNode<T> {
  value: T;
  left: BinaryTreeNode<T> | null;
  right: BinaryTreeNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinaryTree<T> {
  root: BinaryTreeNode<T> | null;

  constructor(root: BinaryTreeNode<T> | null = null) {
    this.root = root;
  }

  preOrder(): T[] {
    const result: T[] = [];
    this.preOrderHelper(this.root, result);
    return result;
  }

  private preOrderHelper(node: BinaryTreeNode<T> | null, result: T[]): void {
    if (node === null) return;

    result.push(node.value);
    this.preOrderHelper(node.left, result);
    this.preOrderHelper(node.right, result);
  }

  inOrder(): T[] {
    const result: T[] = [];
    this.inOrderHelper(this.root, result);
    return result;
  }

  private inOrderHelper(node: BinaryTreeNode<T> | null, result: T[]): void {
    if (node === null) return;

    this.inOrderHelper(node.left, result);
    result.push(node.value);
    this.inOrderHelper(node.right, result);
  }

  postOrder(): T[] {
    const result: T[] = [];
    this.postOrderHelper(this.root, result);
    return result;
  }

  private postOrderHelper(node: BinaryTreeNode<T> | null, result: T[]): void {
    if (node === null) return;

    this.postOrderHelper(node.left, result);
    this.postOrderHelper(node.right, result);
    result.push(node.value);
  }

  levelOrder(): T[] {
    if (this.root === null) return [];

    const queue: BinaryTreeNode<T>[] = [this.root];
    const result: T[] = [];
    let front = 0;

    while (front < queue.length) {
      const node = queue[front];
      front++;

      result.push(node.value);

      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }

    return result;
  }
}

class BinaryTreeNode(
    val value: Int,
    var left: BinaryTreeNode? = null,
    var right: BinaryTreeNode? = null
)

fun preorder(root: BinaryTreeNode?): List<Int> {
    val result = mutableListOf<Int>()

    fun dfs(node: BinaryTreeNode?) {
        if (node == null) return

        result.add(node.value)
        dfs(node.left)
        dfs(node.right)
    }

    dfs(root)
    return result
}

fun inorder(root: BinaryTreeNode?): List<Int> {
    val result = mutableListOf<Int>()

    fun dfs(node: BinaryTreeNode?) {
        if (node == null) return

        dfs(node.left)
        result.add(node.value)
        dfs(node.right)
    }

    dfs(root)
    return result
}

fun postorder(root: BinaryTreeNode?): List<Int> {
    val result = mutableListOf<Int>()

    fun dfs(node: BinaryTreeNode?) {
        if (node == null) return

        dfs(node.left)
        dfs(node.right)
        result.add(node.value)
    }

    dfs(root)
    return result
}

fun levelOrder(root: BinaryTreeNode?): List<Int> {
    if (root == null) return emptyList()

    val result = mutableListOf<Int>()
    val queue = ArrayDeque<BinaryTreeNode>()

    queue.addLast(root)

    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        result.add(node.value)

        if (node.left != null) queue.addLast(node.left!!)
        if (node.right != null) queue.addLast(node.right!!)
    }

    return result
}

final class BinaryTreeNode<T> {
    var value: T
    var left: BinaryTreeNode<T>?
    var right: BinaryTreeNode<T>?

    init(_ value: T) {
        self.value = value
        self.left = nil
        self.right = nil
    }
}

final class BinaryTree<T> {
    var root: BinaryTreeNode<T>?

    init(root: BinaryTreeNode<T>? = nil) {
        self.root = root
    }

    func preOrder() -> [T] {
        var result: [T] = []
        preOrderHelper(root, &result)
        return result
    }

    private func preOrderHelper(_ node: BinaryTreeNode<T>?, _ result: inout [T]) {
        guard let node = node else { return }

        result.append(node.value)
        preOrderHelper(node.left, &result)
        preOrderHelper(node.right, &result)
    }

    func inOrder() -> [T] {
        var result: [T] = []
        inOrderHelper(root, &result)
        return result
    }

    private func inOrderHelper(_ node: BinaryTreeNode<T>?, _ result: inout [T]) {
        guard let node = node else { return }

        inOrderHelper(node.left, &result)
        result.append(node.value)
        inOrderHelper(node.right, &result)
    }

    func postOrder() -> [T] {
        var result: [T] = []
        postOrderHelper(root, &result)
        return result
    }

    private func postOrderHelper(_ node: BinaryTreeNode<T>?, _ result: inout [T]) {
        guard let node = node else { return }

        postOrderHelper(node.left, &result)
        postOrderHelper(node.right, &result)
        result.append(node.value)
    }

    func levelOrder() -> [T] {
        guard let root = root else { return [] }

        var queue: [BinaryTreeNode<T>] = [root]
        var result: [T] = []
        var front = 0

        while front < queue.count {
            let node = queue[front]
            front += 1

            result.append(node.value)

            if let left = node.left {
                queue.append(left)
            }
            if let right = node.right {
                queue.append(right)
            }
        }

        return result
    }
}

using System.Collections.Generic;

public class BinaryTreeNode
{
    public int Value;
    public BinaryTreeNode Left;
    public BinaryTreeNode Right;

    public BinaryTreeNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

public class BinaryTreeTraversals
{
    public List<int> Preorder(BinaryTreeNode root)
    {
        List<int> result = new List<int>();
        PreorderDfs(root, result);
        return result;
    }

    private void PreorderDfs(BinaryTreeNode node, List<int> result)
    {
        if (node == null) return;

        result.Add(node.Value);
        PreorderDfs(node.Left, result);
        PreorderDfs(node.Right, result);
    }

    public List<int> Inorder(BinaryTreeNode root)
    {
        List<int> result = new List<int>();
        InorderDfs(root, result);
        return result;
    }

    private void InorderDfs(BinaryTreeNode node, List<int> result)
    {
        if (node == null) return;

        InorderDfs(node.Left, result);
        result.Add(node.Value);
        InorderDfs(node.Right, result);
    }

    public List<int> Postorder(BinaryTreeNode root)
    {
        List<int> result = new List<int>();
        PostorderDfs(root, result);
        return result;
    }

    private void PostorderDfs(BinaryTreeNode node, List<int> result)
    {
        if (node == null) return;

        PostorderDfs(node.Left, result);
        PostorderDfs(node.Right, result);
        result.Add(node.Value);
    }

    public List<int> LevelOrder(BinaryTreeNode root)
    {
        List<int> result = new List<int>();

        if (root == null) return result;

        Queue<BinaryTreeNode> queue = new Queue<BinaryTreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            BinaryTreeNode node = queue.Dequeue();
            result.Add(node.Value);

            if (node.Left != null) queue.Enqueue(node.Left);
            if (node.Right != null) queue.Enqueue(node.Right);
        }

        return result;
    }
}

package main

type BinaryTreeNode struct {
    Value int
    Left  *BinaryTreeNode
    Right *BinaryTreeNode
}

type BinaryTree struct {
    Root *BinaryTreeNode
}

func NewBinaryTreeNode(value int) *BinaryTreeNode {
    return &BinaryTreeNode{Value: value}
}

func (tree *BinaryTree) PreOrder() []int {
    result := []int{}
    preOrderHelper(tree.Root, &result)
    return result
}

func preOrderHelper(node *BinaryTreeNode, result *[]int) {
    if node == nil {
        return
    }

    *result = append(*result, node.Value)
    preOrderHelper(node.Left, result)
    preOrderHelper(node.Right, result)
}

func (tree *BinaryTree) InOrder() []int {
    result := []int{}
    inOrderHelper(tree.Root, &result)
    return result
}

func inOrderHelper(node *BinaryTreeNode, result *[]int) {
    if node == nil {
        return
    }

    inOrderHelper(node.Left, result)
    *result = append(*result, node.Value)
    inOrderHelper(node.Right, result)
}

func (tree *BinaryTree) PostOrder() []int {
    result := []int{}
    postOrderHelper(tree.Root, &result)
    return result
}

func postOrderHelper(node *BinaryTreeNode, result *[]int) {
    if node == nil {
        return
    }

    postOrderHelper(node.Left, result)
    postOrderHelper(node.Right, result)
    *result = append(*result, node.Value)
}

func (tree *BinaryTree) LevelOrder() []int {
    if tree.Root == nil {
        return []int{}
    }

    queue := []*BinaryTreeNode{tree.Root}
    result := []int{}
    front := 0

    for front < len(queue) {
        node := queue[front]
        front++

        result = append(result, node.Value)

        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }

    return result
}

Time and Space Complexity

Operation	Time	Space
DFS Traversal	O(n)	O(h) recursion stack
BFS Traversal	O(n)	O(n) queue in worst case
BST Search	O(log n) average, O(n) worst	O(h) recursive, O(1) iterative
BST Insert	O(log n) average, O(n) worst	O(h) recursive, O(1) iterative
BST Delete	O(log n) average, O(n) worst	O(h) recursive, O(1) iterative

N-ary Tree

An N-ary Tree is a tree where each node can have up to N children, where N is a fixed positive integer

N = 2 → Binary Tree

N = 3 → Ternary Tree

N = 10 → Decary Tree

Each node typically contains a value and a collection of child references.

Degree: Number of children a node has.

class NaryTreeNode {
  constructor(value) {
    this.value = value;
    this.children = []; // Array of child nodes
  }
}

from typing import Any


class NaryTreeNode:
    def __init__(self, value: Any):
        self.value = value
        self.children: list["NaryTreeNode"] = []  # List of child nodes

import java.util.ArrayList;
import java.util.List;

class NaryTreeNode<T> {
    T value;
    List<NaryTreeNode<T>> children;

    NaryTreeNode(T value) {
        this.value = value;
        this.children = new ArrayList<>(); // List of child nodes
    }
}

#include<vector>
using namespace std;

template <typename T>
class NaryTreeNode {
public:
    T value;
    vector<NaryTreeNode<T>*> children; // List of child nodes

    NaryTreeNode(T value) {
        this->value = value;
    }
};

#include<stdlib.h>

typedef struct NaryTreeNode {
    int value;
    struct NaryTreeNode** children; // Array of child node pointers
    int childCount;
    int childCapacity;
} NaryTreeNode;

NaryTreeNode* createNaryTreeNode(int value) {
    NaryTreeNode* node = (NaryTreeNode*)malloc(sizeof(NaryTreeNode));
    if (node == NULL) return NULL;

    node->value = value;
    node->childCount = 0;
    node->childCapacity = 4;
    node->children = (NaryTreeNode**)malloc(sizeof(NaryTreeNode*) * node->childCapacity);

    if (node->children == NULL) {
        free(node);
        return NULL;
    }

    return node;
}

void addNaryChild(NaryTreeNode* parent, NaryTreeNode* child) {
    if (parent == NULL || child == NULL) return;

    if (parent->childCount == parent->childCapacity) {
        parent->childCapacity *= 2;
        NaryTreeNode** newChildren = (NaryTreeNode**)realloc(
            parent->children,
            sizeof(NaryTreeNode*) * parent->childCapacity
        );
        if (newChildren == NULL) return;

        parent->children = newChildren;
    }

    parent->children[parent->childCount] = child;
    parent->childCount++;
}

void freeNaryTree(NaryTreeNode* root) {
    if (root == NULL) return;

    for (int i = 0; i < root->childCount; i++) {
        freeNaryTree(root->children[i]);
    }

    free(root->children);
    free(root);
}

class NaryTreeNode<T> {
  value: T;
  children: NaryTreeNode<T>[];

  constructor(value: T) {
    this.value = value;
    this.children = []; // Array of child nodes
  }
}

class NaryTreeNode(
    val value: Int,
    val children: MutableList<NaryTreeNode> = mutableListOf()
)

final class NaryTreeNode<T> {
    var value: T
    var children: [NaryTreeNode<T>] // Array of child nodes

    init(_ value: T) {
        self.value = value
        self.children = []
    }
}

using System.Collections.Generic;

public class NaryTreeNode
{
    public int Value;
    public List<NaryTreeNode> Children;

    public NaryTreeNode(int value)
    {
        Value = value;
        Children = new List<NaryTreeNode>();
    }
}

package main

type NaryTreeNode struct {
    Value    int
    Children []*NaryTreeNode // Slice of child nodes
}

func NewNaryTreeNode(value int) *NaryTreeNode {
    return &NaryTreeNode{
        Value:    value,
        Children: []*NaryTreeNode{},
    }
}

         A
      /  |  \
     B   C   D
    / \     / \
   E   F   G   H

A has 3 children → B, C, D

B has 2 children → E, F

D has 2 children → G, H

Three Important Types

Trie (Prefix Tree): Ordered N-ary tree optimized for string prefix lookups
B-tree: A balanced multi-way search tree optimized for disk-based storage and indexing, commonly used in databases and file systems

Use Case of N-ary tree	Explanation
File Systems	Folder structures can be modeled as general trees because each folder can contain multiple files or subfolders
HTML DOM Tree	Elements can have multiple children
Trie (Prefix Tree)	A tree-like structure where each edge or child position represents a character from the alphabet.
Game Trees (AI)	Each game state can lead to multiple next states

Specialized Trees

Some specialized trees are array-based data structures designed for efficient handling of:

Range Queries (sum, min, max)

Frequent Updates

Prefix Computations

Unlike pointer-based trees like binary trees, Fenwick Trees and many Segment Tree implementations structures use arrays to simulate tree behavior, with the entire structure stored in a flat array.

Two Important Types

Binary Indexed Tree (Fenwick Tree)
Efficiently supports prefix sum queries and point updates in O(log n) time. Uses a 1D array of size n + 1 (1-based indexing).
Segment Tree
Supports general range queries (sum, min, max, gcd) and range updates in O(log n) time. Typically stored in an array of size around 4n.

Real World Applications	Application
Stock Analysis	Daily price updates + range queries
Game Engines	Range health, buffs, area-of-effect
Data Analysis	Statistics Frequency tables and cumulative frequency queries
Competitive Programming	Range Sum/Min/Max queries

Concept	Tree	Graph
Preorder/Postorder	✅	Sometimes
DFS / BFS Traversal	✅	✅
Can have cycles	❌	✅
Parent-child structure	✅	Sometimes