Data Structure – Trees

1 Introduction to Trees

What is a tree data structure?

A tree data structure is a hierarchical model that organizes data as nodes connected by edges. It begins with a single root node and branches into child nodes. Unlike a linear data structure such as an array, linked list, stack, or queue, a tree represents one-to-many relationships and multiple levels of data.

A tree is useful when the data naturally forms a hierarchy. Common examples include a computer file system, an organization chart, an HTML document, a database index, a family tree, and the category structure of a website.

Definition and Structure

1. Hierarchical Organization:
   A tree is used to represent data with a natural hierarchy. Each tree consists of nodes connected by edges. The topmost node is called the root, and every other node in the tree has a parent node and may have zero or more child nodes.
2. Nodes and Edges:
   The basic building blocks of a tree are nodes, which store data, and edges, which establish relationships between these nodes. This structure allows trees to model relationships like family ancestries, folder structures, and organizational charts.
3. Connected Structure:
   In a tree, each node is reachable from the root through a unique path. A valid tree does not contain cycles, so following child links cannot lead back to an ancestor.
4. Recursive Structure:
   Every child node and all of its descendants form a smaller tree called a subtree. Many tree algorithms use recursion because each subtree can be processed in the same way as the complete tree.

Basic properties of a tree data structure

• A non-empty tree has exactly one root node.
• Every node except the root has exactly one parent.
• A node may have zero, one, or several children, depending on the type of tree.
• There is exactly one simple path from the root to any node.
• A tree containing n nodes has n - 1 edges.
• A tree does not contain a cycle.

2 Tree Data Structure Terminology

Nodes

The fundamental units or elements of a tree that store data and may connect to other nodes.

Edges

The connections or links between nodes that define the relationship between parent and child nodes.

Root

The topmost node of a tree, which does not have a parent. It serves as the starting point for the tree structure.

Leaf

A node that does not have any children. Leaf nodes typically mark the end of a branch in the tree.

Internal Node

A node that has at least one child. The root is also an internal node when it has children.

Parent

A node that has one or more child nodes directly connected below it in the hierarchy.

Child

A node that is directly connected below another node, called its parent.

Sibling

Nodes that share the same parent node. They exist at the same level in the hierarchy.

Ancestor

Any node on the path from the root to a given node, excluding the node itself. A parent is the nearest ancestor.

Descendant

Any node reachable by repeatedly following child links from a given node. A child is the nearest descendant.

Subtree

A node together with all of its descendants. Each child of a node is the root of a subtree.

Path

A sequence of nodes connected by edges. The path length is normally measured by the number of edges in the path.

Depth

The number of edges from the root node to a specific node. The root has depth 0.

Height

The length of the longest downward path from a node to a leaf. Under the edge-based convention, a leaf has height 0.

Levels

The different layers or tiers in a tree, starting from the root. When the root is assigned level 0, a node’s level equals its depth.

Degree

The number of children a node has. The degree of a tree is the maximum degree of any node in that tree.

Forest

A collection of separate trees. Removing the root of a tree produces a forest consisting of its child subtrees.

Depth and height conventions: Some books count nodes rather than edges when defining height or level. State the convention being used before solving a problem. This tutorial uses edge-based depth and height, with the root at depth 0 and a leaf at height 0.

3 Tree Representations

Linked representations

In Linked representations, each node in the tree is typically represented by an object or a structure that contains data and pointers (or references) to its child nodes.

In a linked representation, every node in the tree is created as a separate entity that “links” to its children.

For example, in a binary tree (a common type of tree where each node has at most two children), each node contains:

• Data: The value or information stored in the node.
• Left Pointer: A reference to the left child node.
• Right Pointer: A reference to the right child node.

For trees that are not strictly binary, you might have a list or an array of pointers to all child nodes.

Consider a simple binary tree node written in a language like Python:

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

In this example:

• data holds the integer value.
• left is a pointer to the left child.
• right is a pointer to the right child.

Imagine we want to build a simple tree with the following structure:

      10
     /  \
    5    15
    

Step 1: Create the root node.

root = TreeNode(10)

Step 2: Create the left and right child nodes.

root.left = TreeNode(5)
root.right = TreeNode(15)

Now, root is a node containing the value 10, with its left child pointing to a node containing 5 and its right child pointing to a node containing 15.

Visualize the tree as follows:

       [10]
       /  \
    [5]    [15]
    

Each node “knows” about its children through pointers. This direct linkage makes it easy to traverse the tree, add nodes, or modify the structure dynamically.

Benefits of Linked Representations:

• Dynamic Memory Allocation: Nodes are created on the heap, allowing the tree to grow as needed without allocating a large contiguous block of memory.
  
• Easy Modification: Adding or removing nodes is straightforward because you only update a few pointers.
  
• Intuitive Structure: The linked representation mirrors the natural hierarchical structure of trees, making the code easier to understand and maintain.

Array Representations of Tree

While linked representations use nodes with pointers, array representations store tree elements in a contiguous block of memory. This method is especially common for complete binary trees, where the structure of the tree allows you to calculate the position of parent and child nodes using simple arithmetic.

In an array representation of a binary tree, if a node is stored at index i:

• left child is stored at index 2*i + 1
• right child is stored at index 2*i + 2
• parent is stored at index (i - 1) // 2

Let’s see how this works with a Python example.

Consider a binary tree structured like this:

          10
         /  \
        5    15
       / \
      3   7
    

We can represent this tree in an array as:

tree = [10, 5, 15, 3, 7]

In this array:

• The root 10 is at index 0.
• The left child of 10 is 5 at index 1 (2*0+1=1).
• The right child of 10 is 15 at index 2 (2*0+2=2).
• The left child of 5 is 3 at index 3 (2*1+1=3).
• The right child of 5 is 7 at index 4 (2*1+2=4).
  

To access these nodes programmatically, you can write simple functions in Python. For example:

def get_left_child(index, tree):
    child_index = 2 * index + 1
    if child_index < len(tree):
        return tree[child_index]
    return None

def get_right_child(index, tree):
    child_index = 2 * index + 2
    if child_index < len(tree):
        return tree[child_index]
    return None

# Example usage:
tree = [10, 5, 15, 3, 7]
print("Left child of 10:", get_left_child(0, tree))   # Outputs 5
print("Right child of 10:", get_right_child(0, tree))  # Outputs 15
    

This approach leverages the properties of complete binary trees to efficiently compute child and parent positions using simple index calculations.

Note: Array representations work best when the tree is complete (all levels are fully filled except possibly the last, which is filled from left to right). For sparse trees, this method might waste space as many positions in the array could be unused.

Linked tree versus array tree representation

Factor	Linked representation	Array representation
Best suited to	Dynamic, irregular, or sparse trees	Complete or nearly complete binary trees
Child access	Through stored references	Through index formulas
Insertion and deletion	Usually requires changing references	May require shifting or managing empty positions
Memory overhead	Requires one or more references per node	May waste slots when the tree is sparse
Memory locality	Nodes may be distributed in memory	Elements are stored contiguously
Common use	BSTs, tries, general trees	Binary heaps and complete binary trees

4 Types of Trees

General Tree

A general tree is a tree data structure where each node can have an arbitrary number of children. It is flexible and can model hierarchies that are not strictly binary.

class GeneralTreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []

# Example: Creating a general tree node with two children
root = GeneralTreeNode("Root")
child1 = GeneralTreeNode("Child 1")
child2 = GeneralTreeNode("Child 2")
root.children.append(child1)
root.children.append(child2)

This example shows a basic node for a general tree where the children attribute is a list that can hold any number of child nodes.

Binary Tree

A binary tree is a tree structure in which each node has at most two children, commonly referred to as the left child and the right child.

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Example: Creating a simple binary tree
root = BinaryTreeNode(10)
root.left = BinaryTreeNode(5)
root.right = BinaryTreeNode(15)

This code creates a binary tree with a root node of 10, a left child of 5, and a right child of 15. Each node has at most two children.

Binary Search Tree (BST)

A Binary Search Tree is a binary tree where for every node, the values in the left subtree are less than the node’s value, and the values in the right subtree are greater.

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def insert(root, data):
    if root is None:
        return BSTNode(data)
    if data < root.data:
        root.left = insert(root.left, data)
    else:
        root.right = insert(root.right, data)
    return root

# Example: Inserting elements into a BST
root = BSTNode(10)
insert(root, 5)
insert(root, 15)
insert(root, 3)
insert(root, 7)

This BST example includes an insertion function that places new nodes into the tree based on their value, maintaining the BST property. The treatment of duplicate values must be defined by the implementation; common choices are to reject them, count occurrences, or consistently place them on one side.

AVL Tree

An AVL Tree is a self-balancing Binary Search Tree where the height difference between the left and right subtrees (balance factor) is at most one for all nodes.

class AVLNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

def get_height(node):
    return node.height if node else 0

def right_rotate(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = max(get_height(y.left), get_height(y.right)) + 1
    x.height = max(get_height(x.left), get_height(x.right)) + 1
    return x

# Example: Performing a right rotation
node = AVLNode(30)
node.left = AVLNode(20)
node.left.left = AVLNode(10)
rotated_root = right_rotate(node)

This snippet demonstrates a right rotation in an AVL Tree, which is one of the key operations used to maintain tree balance after insertions or deletions.

Red-Black Tree

A Red-Black Tree is a self-balancing Binary Search Tree that uses an extra bit (red or black) to ensure the tree remains approximately balanced during insertions and deletions.

class RBNode:
    def __init__(self, data, color="red"):
        self.data = data
        self.color = color  # "red" or "black"
        self.left = None
        self.right = None
        self.parent = None

# Note: A full implementation involves additional functions for rotations and color fixes.
# This is a simplified node structure for a Red-Black Tree.

This simplified example shows the node structure for a Red-Black Tree. A complete implementation would include rotation and color-fixing methods to maintain the red-black properties.

B-Tree

B-Trees are self-balancing trees that generalize the concept of binary search trees by allowing more than two children per node. They are commonly used in databases and file systems.

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # Minimum degree (defines the range for number of keys)
        self.keys = []
        self.children = []
        self.leaf = leaf

# Example: Creating a B-Tree node with minimum degree 3
node = BTreeNode(t=3, leaf=True)

This example demonstrates the basic structure of a B-Tree node. The node can hold multiple keys and has multiple children, which reduces tree height and the number of storage-page accesses required for large collections of data.

Heap

A Heap is a specialized tree-based data structure that satisfies the heap property. In a min-heap, every parent node is less than or equal to its children; in a max-heap, every parent node is greater than or equal to its children.

import heapq

# Example: Creating and using a min-heap in Python
heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 15)
min_value = heapq.heappop(heap)  # Returns 5, the smallest element

This example uses Python’s built-in heapq module to demonstrate a min-heap, where the smallest element is always at the root and can be efficiently retrieved. A heap is not a binary search tree: it orders parents relative to children but does not fully order the left and right subtrees.

Trie (Prefix Tree)

A Trie, or prefix tree, is a specialized tree used to store associative data structures, typically strings. It allows efficient retrieval of words by their prefixes.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

# Example: Inserting words into a Trie
trie = Trie()
trie.insert("hello")
trie.insert("helium")

This code sets up a Trie for storing strings and demonstrates how to insert words. Each node represents a character, and paths down the tree represent words.

Segment Tree

A Segment Tree stores aggregate information about ranges of an array. Depending on the operation maintained at each node, it can support range-sum, range-minimum, range-maximum, or similar queries along with point or range updates.

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        # Build the tree by inserting leaves
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, l, r):
        l += self.n
        r += self.n
        result = 0
        while l < r:
            if l % 2:
                result += self.tree[l]
                l += 1
            if r % 2:
                r -= 1
                result += self.tree[r]
            l //= 2
            r //= 2
        return result

# Example: Creating a segment tree and querying a range
data = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(data)
print("Sum of values in range [1, 5):", seg_tree.query(1, 5))

This segment tree example builds a tree for range sum queries. The query(l, r) method uses a half-open interval, so it includes index l and excludes index r.

Binary tree classifications by shape

Binary tree type	Defining property
Full binary tree	Every node has either zero or two children.
Complete binary tree	Every level except possibly the last is full, and nodes on the last level are placed from left to right.
Perfect binary tree	Every internal node has two children and all leaves occur at the same depth.
Balanced binary tree	The height is kept proportional to the logarithm of the number of nodes according to the balance rule used by that tree.
Degenerate tree	Each internal node has only one child, causing the structure to behave like a linked list.
Skewed tree	A degenerate tree in which nodes continue primarily on the left or primarily on the right.

5 Tree Traversal Algorithms

Traversal means visiting every node of a tree in a defined order. Depth-first traversal follows a branch before backtracking, while breadth-first traversal processes nodes one level at a time.

Preorder, inorder, postorder, and level-order traversal

        10
       /  \
      5    15
     / \     \
    3   7     20

Traversal	Visit order	Result for the example	Typical use
Preorder	Root, left subtree, right subtree	10, 5, 3, 7, 15, 20	Copying or serializing a tree
Inorder	Left subtree, root, right subtree	3, 5, 7, 10, 15, 20	Reading a BST in sorted order
Postorder	Left subtree, right subtree, root	3, 7, 5, 20, 15, 10	Deleting a tree or evaluating expression trees
Level order	Nodes level by level	10, 5, 15, 3, 7, 20	Shortest-level discovery and breadth-first processing

Python implementation of tree traversals

from collections import deque


def preorder(node):
    if node is None:
        return
    print(node.data, end=" ")
    preorder(node.left)
    preorder(node.right)


def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.data, end=" ")
    inorder(node.right)


def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.data, end=" ")


def level_order(root):
    if root is None:
        return

    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.data, end=" ")

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

Each traversal visits every node once, so its time complexity is O(n) for a tree with n nodes. Recursive depth-first traversal uses O(h) call-stack space, where h is the tree height. Level-order traversal uses a queue whose size depends on the maximum width of the tree.

6 Binary Search Tree Operations

A binary search tree supports searching, insertion, and deletion by comparing a target key with the current node. Smaller keys are followed through the left subtree and larger keys through the right subtree.

Searching for a value in a binary search tree

def search_bst(root, target):
    current = root

    while current is not None:
        if target == current.data:
            return current
        if target < current.data:
            current = current.left
        else:
            current = current.right

    return None

The search follows only one root-to-leaf path. Its running time is O(h), where h is the height of the BST. This becomes O(log n) in a balanced tree but can degrade to O(n) in a skewed tree.

Deleting a node from a binary search tree

BST deletion has three cases:

1. Leaf node: Remove the node directly.
2. One child: Replace the node with its only child.
3. Two children: Replace the node’s value with its inorder successor, usually the smallest value in the right subtree, and then delete that successor.

def minimum_node(node):
    current = node
    while current.left is not None:
        current = current.left
    return current


def delete_bst(root, target):
    if root is None:
        return None

    if target < root.data:
        root.left = delete_bst(root.left, target)
    elif target > root.data:
        root.right = delete_bst(root.right, target)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left

        successor = minimum_node(root.right)
        root.data = successor.data
        root.right = delete_bst(root.right, successor.data)

    return root

Deletion also takes O(h) time because it follows one or more paths whose lengths are bounded by the height of the tree.

7 Tree Operation Complexity

Tree or operation	Typical time	Worst-case time	Important condition
Traverse any tree	O(n)	O(n)	Every node is visited
Search an unordered binary tree	O(n)	O(n)	No ordering rule guides the search
Search, insert, or delete in a BST	O(log n)	O(n)	Depends on tree height
Search, insert, or delete in an AVL tree	O(log n)	O(log n)	Rotations maintain strict balance
Search, insert, or delete in a Red-Black tree	O(log n)	O(log n)	Color and rotation rules bound height
Find minimum in a binary min-heap	O(1)	O(1)	Minimum is stored at the root
Insert into or remove root from a heap	O(log n)	O(log n)	Heap order is restored along a path
Trie operation for a key of length m	O(m)	O(m)	Cost depends on key length
Segment-tree range query	O(log n)	O(log n)	For standard associative range aggregates

Complexity claims for trees should be tied to height. A plain BST does not automatically provide logarithmic performance. If sorted values are inserted into an unbalanced BST, it may become skewed and behave like a linked list.

8 Applications of Tree Data Structures

Application	How a tree is used	Common tree type
File systems	Directories contain files and nested directories	General tree
Web documents	HTML elements form a Document Object Model hierarchy	General tree
Database indexes	Keys are organized to reduce storage accesses during lookup	B-Tree or B+ Tree
Priority queues	The highest- or lowest-priority item remains at the root	Binary heap
Autocomplete and dictionaries	Words share paths according to common prefixes	Trie
Compilers and calculators	Operators and operands form syntax or expression hierarchies	Syntax tree or expression tree
Routing and decision systems	Each branch represents a choice or test result	Decision tree
Range-query processing	Nodes store aggregates for array intervals	Segment tree
Organization charts	Employees or departments are grouped under supervisors	General tree
Game and AI search	Nodes represent states and edges represent possible moves	Search tree

Tree data structure real-life example

Consider a file-system hierarchy:

Documents
├── Work
│   ├── report.docx
│   └── budget.xlsx
└── Personal
    ├── photos
    └── notes.txt

Documents is the root, Work and Personal are children and siblings, and the files are leaf nodes. The subtree rooted at Work contains that directory and everything stored below it.

9 Advantages and Limitations of Trees

Advantages of tree data structures

• Represent hierarchical and recursive relationships directly.
• Allow efficient search, insertion, and deletion when an appropriate balanced tree is used.
• Support ordered processing through traversals such as inorder and level order.
• Can grow dynamically in a linked representation.
• Provide specialized structures for priorities, prefixes, indexing, and range queries.

Limitations of tree data structures

• Pointer-based nodes require additional memory for references and metadata.
• Recursive algorithms can exhaust the call stack when a tree becomes very deep.
• An unbalanced BST can lose its expected logarithmic performance.
• Deletion and rebalancing logic can be more complex than operations on arrays or linked lists.
• Array representation can waste memory when the tree is sparse.

10 Choosing the Appropriate Tree Type

Requirement	Suitable tree
Represent an unrestricted hierarchy	General tree
Maintain dynamically ordered keys	Balanced BST such as AVL or Red-Black tree
Frequently retrieve the minimum or maximum item	Min-heap or max-heap
Store words and perform prefix search	Trie
Index records stored in blocks or pages	B-Tree or B+ Tree
Answer repeated aggregate queries over array ranges	Segment tree
Store a complete binary tree compactly	Array representation
Model operators and operands	Expression tree

The correct tree depends on the required operations. A heap is appropriate for priority access but not arbitrary ordered search. A trie is useful for prefixes but may use substantial memory. A balanced BST supports ordered updates, while a B-Tree is designed to keep the structure shallow when data is stored in blocks.

11 Frequently Asked Questions about Trees

Which data structure is used to implement a tree?

A tree is commonly implemented using linked nodes containing references to their children. Complete binary trees, especially heaps, are commonly stored in arrays because parent and child positions can be calculated from indexes.

What are the main applications of tree data structures?

Trees are used for file systems, database indexes, HTML document models, organization charts, priority queues, autocomplete systems, expression evaluation, decision-making systems, and efficient range queries.

What are four common types of trees?

Four common categories are general trees, binary trees, binary search trees, and balanced search trees such as AVL or Red-Black trees. Other important specialized types include heaps, tries, B-Trees, and segment trees.

How do you create a tree data structure?

Define a node that stores a value and one or more child references, create the root node, create additional nodes, and connect them through those references. For an array-based complete binary tree, store nodes in level order and use index formulas to locate parents and children.

What is the difference between a binary tree and a binary search tree?

A binary tree only restricts each node to at most two children. A binary search tree adds an ordering rule: keys in the left subtree precede the node’s key, while keys in the right subtree follow it according to the chosen comparison policy.

12 Tree Data Structure Editorial QA Checklist

• Confirm that every illustrated tree has one root, no cycle, and a unique root-to-node path.
• State whether depth and height count edges or nodes before presenting numerical answers.
• Do not describe every binary tree as a binary search tree; verify that the ordering property is present.
• Check that inorder traversal is described as sorted only when the tree is a valid BST.
• Verify array child formulas use zero-based indexes: 2i + 1 and 2i + 2.
• Express BST operation complexity as O(h) before converting it to balanced or worst-case bounds.
• Keep heap ordering distinct from BST ordering.
• Document how duplicate keys are handled in BST insertion and deletion examples.
• Check whether range endpoints in segment-tree examples are inclusive, exclusive, or half-open.
• Test traversal and deletion code with an empty tree, a single-node tree, and a skewed tree.

13 Tree Data Structure Summary

A tree organizes nodes through parent-child relationships. Its root provides the starting point, leaves terminate branches, and each node can define a subtree. Trees may be stored through linked references or, for suitable binary-tree shapes, in arrays.

General trees model unrestricted hierarchies, binary trees limit each node to two children, BSTs add an ordering rule, balanced trees control height, heaps support priority access, tries support prefix operations, B-Trees support block-based indexing, and segment trees support range queries. Selecting the right type requires considering the operations, expected tree height, memory layout, and update pattern.