[AlgoMastery]
Topics›Tree›
📖

Tree
~20 min read
5 practice problems

Overview

A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike linear data structures (arrays, linked lists), trees branch out to represent relationships between elements in a parent-child hierarchy. Each node can have zero or more child nodes, with the topmost node called the root.

Trees are fundamental in computer science and are used to represent hierarchical data, organize information, and solve complex problems efficiently. They form the basis for many advanced algorithms and data structures like binary trees, binary search trees, and heaps.

Key characteristics:

  • Hierarchical structure - Parent-child relationships
  • Root node - Topmost node with no parent
  • Leaf nodes - Nodes with no children
  • Internal nodes - Nodes with children
  • Path - Sequence of nodes from parent to child
  • Depth - Distance from root to node (0 for root)
  • Height - Maximum depth of tree

Tree Terminology

Basic Terms

  • Root: Topmost node in the tree
  • Parent: Node that has children
  • Child: Node that is connected to a parent
  • Leaf: Node with no children (terminal node)
  • Sibling: Nodes with same parent
  • Ancestor: Any node on path from root to node
  • Descendant: Any node on path from node to leaves
  • Subtree: Tree rooted at any node

Tree Properties

  • Degree of node: Number of children
  • Degree of tree: Maximum degree among all nodes
  • Height: Longest path from root to leaf
  • Level: Distance from root (root is level 0)
  • Path: Sequence of nodes connecting parent to child

Tree Traversal Methods

Depth-First Traversals

  1. Preorder (Root → Left → Right)
  2. Inorder (Left → Root → Right) - Only applicable to binary trees
  3. Postorder (Left → Right → Root)

Breadth-First Traversal

  1. Level-order (Visit nodes level by level from top to bottom)

Binary Tree Properties

Structure

  • Each node has at most 2 children (left and right)
  • Can be empty (no nodes)
  • Has exactly one root node

Types of Binary Trees

  1. Full Binary Tree: Every node has 0 or 2 children
  2. Complete Binary Tree: All levels filled except possibly last, with leftmost arrangement
  3. Perfect Binary Tree: All internal nodes have 2 children and all leaves at same level
  4. Balanced Binary Tree: Height difference between subtrees is minimal

Properties

  • Maximum nodes at level i: 2^i (0-indexed)
  • Maximum nodes in tree of height h: 2^(h+1) - 1
  • Minimum nodes in tree of height h: h + 1
  • Height of complete binary tree with n nodes: ⌊log₂(n)⌋

Binary Tree Representation

Array Representation (Complete Binary Tree)

  • Root at index 0
  • For node at index i:
    • Left child at index 2*i + 1
    • Right child at index 2*i + 2
    • Parent at index ⌊(i-1)/2⌋

Linked List Representation

class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  constructor(val: T) {
    this.val = val;
  }
}

Advantages of linked list:

  • Dynamic size
  • No memory waste
  • Easy to implement tree operations

Disadvantages:

  • Extra memory for pointers
  • Not cache-friendly like arrays

Common Tree Operations

Core Operations

  1. Insert: Add new node to appropriate position
  2. Search: Find specific value in tree
  3. Delete: Remove node from tree
  4. Traverse: Visit all nodes in specific order
  5. Height/Depth: Calculate tree dimensions
  6. Count Nodes: Count total nodes in tree

Tree Properties Operations

  1. Balance Check: Determine if tree is balanced
  2. Mirror Check: Check if tree is mirror image
  3. Validate BST: Check if tree follows BST property
  4. Find Lowest Common Ancestor (LCA): Find deepest node that is ancestor of two nodes
  5. Find Diameter: Maximum distance between any two nodes

Applications of Trees

  1. File Systems - Hierarchical directory structure
  2. Decision Making - Decision trees in AI/ML
  3. Expression Parsing - Parse and evaluate mathematical expressions
  4. Network Routing - Routing tables in networks
  5. Syntax Trees - Compiler parsing
  6. Game AI - Minimax trees in game playing
  7. Database Indexing - B-trees and B+ trees for indexing
  8. Huffman Coding - Compression algorithms

Time and Space Complexity

Operation Binary Tree Balanced BST
Search O(n) worst case O(log n) average
Insert O(n) worst case O(log n) average
Delete O(n) worst case O(log n) average
Traversal O(n) O(n)
Space O(n) O(n)

Note: Binary trees can degenerate to linked lists (O(n)) if not balanced.

Practice Tips

  1. Understand tree properties - Know how height, depth, and levels relate
  2. Master traversals - Preorder, inorder, postorder for binary trees
  3. Handle edge cases - Empty tree, single node, null nodes
  4. Use recursion - Most tree problems can be solved recursively
  5. Consider balanced trees - Use BST for better performance
  6. Array vs linked list - Choose appropriate representation based on use case
  7. Tree reconstruction - Know how to reconstruct tree from traversals
← PreviousTree OverviewNext →Binary Tree