Tree Data Structure

A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges, where each element can have multiple 'next' elements, allowing the data structure to branch out in various directions. Unlike linear structures (arrays, linked lists), trees organize data hierarchically with one root node and sub-nodes as branches.

Core Terminology and Structure

Basic Components

• Root: The topmost node from which all other nodes originate. Every tree must have exactly one root node.
• Edge: The connecting link between any two nodes. In a tree with N nodes, there are exactly N-1 edges.
• Parent: A node that has branches to other nodes (children).
• Child: A node that descends from a parent node.
• Siblings: Nodes that share the same parent.
• Leaf/Terminal Node: A node with no children (degree zero).

Tree Properties

• Height: The total number of edges from a leaf node to a particular node in the longest path. The height of the root node represents the height of the entire tree.
• Depth: The total number of edges from the root node to a particular node.
• Level: Each step from top to bottom, starting with level 0 (or 1) at the root.
• Path: The sequence of nodes and edges from one node to another.
• Subtree: Each child from a node forms a subtree recursively.

Types of Trees

Binary Tree

Each node has at most two children (left and right child). Properties include:

• Either empty or consists of root node, left subtree, and right subtree
• Height measured as longest distance between root and leaf node

Binary Search Tree (BST)

A special binary tree where:

• Left child's value < parent's value
• Right child's value > parent's value
• Enables efficient searching, insertion, and deletion operations

AVL Tree

A self-balancing BST where the height difference between left and right subtrees is at most one, maintained through rotations.

N-ary Tree

Each node can have at most N children, providing more flexibility than binary trees.

Basic Operations and Code Examples

Tree Node Structure

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      public TreeNode(int val) {
          this.val = val;
          this.left = null;
          this.right = null;
      }
  }

Tree Traversal Algorithms

1. Inorder Traversal (Left-Root-Right)

// Inorder Traversal (Left → Root → Right)
public void inorderTraversal(TreeNode root) {
    if (root != null) {
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }
}

Use Case: Returns nodes in sorted order for BSTs.

2. Preorder Traversal (Root-Left-Right)

public void preorderTraversal(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
}

Use Case: Used for creating tree copies and prefix expressions.

3. Postorder Traversal (Left-Right-Root)

public void postorderTraversal(TreeNode root) {
    if (root != null) {
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.val + " ");
    }
}

4. Level Order Traversal (BFS)

public List<Integer> levelOrderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        result.add(node.val);
        
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return result;
}

Time and Space Complexity Analysis

Tree Operations Complexity

Traversal Complexity

Complexity Analysis Details

The time complexity function for tree traversal can be defined as: T(n) = T(k) + T(n-k-1) + c where k is nodes on one side and n-k-1 on the other.

For skewed trees: T(n) = O(n) For balanced trees: T(n) = O(n) but with better constants.

Applications

• File Systems: Hierarchical directory structures
• Database Indexing: B-trees and B+ trees for efficient data retrieval
• Expression Parsing: Abstract syntax trees for compilers
• Network Routing: Routing tables and decision trees
• Priority Queues: Binary heaps implementation
• Searching and Sorting: Binary search trees for efficient operations

Trees provide efficient hierarchical data organization with logarithmic time complexity for balanced structures, making them fundamental for many computer science applications.