Tree

Description

In computer science, a tree is a hierarchical data structure consisting of nodes, where each node may have zero or more child nodes, and exactly one parent node—except for the root node, which has no parent. Trees are widely used for organizing and representing data that naturally forms hierarchies, such as file systems, organizational charts, and abstract syntax trees.

Trees enable efficient searching, insertion, and deletion operations and form the basis of many algorithms and data structures, including binary search trees, heaps, and tries.

Basic Terminology

Term	Description
Node	Fundamental unit containing data and links
Root	The topmost node with no parent
Child	A node directly connected below another node
Parent	The node directly above a child node
Leaf	A node with no children
Edge	Connection between two nodes
Subtree	A node and all its descendants
Depth	Number of edges from root to the node
Height	Length of the longest path from node to a leaf
Degree	Number of children of a node

Types of Trees

1. Binary Tree

Each node has at most two children (left and right).
Often used in search and sorting algorithms.

2. Binary Search Tree (BST)

Binary tree with ordered property:
- Left child < parent < right child.
Enables fast lookup, insertion, and deletion (average O(log n)).

3. Balanced Trees

Ensures tree height remains logarithmic relative to number of nodes.
Examples: AVL Trees, Red-Black Trees, B-Trees.

4. Heap

Complete binary tree satisfying heap property:
- Max-heap: parent ≥ children
- Min-heap: parent ≤ children
Used in priority queues and sorting.

5. Trie (Prefix Tree)

Tree for storing strings where each node represents a character.
Efficient for prefix searches and autocomplete.

6. N-ary Tree

Nodes can have any number of children.
Useful for general hierarchies.

Common Tree Traversals

Traversal	Description	Order Example
Preorder	Visit node, left subtree, right subtree	Root, Left, Right
Inorder	Left subtree, node, right subtree	Left, Root, Right
Postorder	Left subtree, right subtree, node	Left, Right, Root
Level-order	Visit nodes level by level (BFS)	Top to bottom, left to right

Tree Operations

Insertion: Add a new node to the tree.
Deletion: Remove a node, restructure as necessary.
Search: Find if a value exists.
Traversal: Visit nodes in a specific order.
Balancing: Reorganize tree to maintain efficiency.

Applications of Trees

File Systems: Directory structures form a tree.
Databases: Indexing with B-Trees.
Compilers: Abstract Syntax Trees (AST) for parsing code.
Networking: Routing tables.
AI: Decision trees and game trees.
XML/JSON Parsing: Document Object Model (DOM) trees.

Implementing a Binary Tree in Python

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

# Example Usage
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder(root)