Data Structure: Tree - Good At Coding

Definition

A tree is a non-linear data structure consisting of a finite set of n (n≥0) nodes:

When n=0, it is called an “empty tree”;
When n>0, there is one and only one root node , and the remaining nodes are divided into several disjoint subsets, each of which is still a tree (called a “subtree”).

Key terms

the term	definition
Root node	The topmost node of a tree, with no parent node (like the “root directory” of a file system).
Parent node/child node	If node A directly contains node B, then A is the parent node of B, and B is the child node of A (parent and child are direct relationships).
sibling nodes	Child nodes of the same parent node are called siblings (like sibling files in the same folder).
leaf node	A node with no children (the “end” of the tree).
Depth	The path length from the root node to the current node (root node depth = 0 or 1, subject to scenario conventions).
Height	The path length from the current node to the farthest leaf node (leaf node height = 0).
Number of floors (Level)	The root node is at level 1 (or level 0), and the number of child nodes is equal to the number of parent nodes plus 1 (corresponding to the depth).
Subtree	A tree consisting of all descendant nodes rooted at a given node (including the given node).

The core characteristics of trees

Acyclicity : There is one and only one path between any two nodes (there is no cycle).
Hierarchical arrangement : Nodes are arranged in a hierarchical manner according to the “parent-child relationship”, with the root at the top and the leaves at the bottom;
Uniqueness : There is one and only one root node, and all non-root nodes have one and only one parent node.

Common tree classification

1. Divide by the number of node subtrees

Binary tree : Each node has at most 2 child nodes (left subtree and right subtree), and it is the most commonly used tree structure;
- Special binary trees: full binary tree (all leaf nodes are on the same level, and non-leaf nodes have 2 child nodes) and complete binary tree (numbered in level order, consistent with the numbering of a full binary tree, missing right nodes but not left nodes).
Multi-way tree : Each node can have multiple child nodes (such as ternary tree, N-way tree);
- Typical applications: file system (directory tree), Trie tree (prefix tree).

2. Classified according to special rules

Binary Search Tree (BST) : The value of all nodes in the left subtree is less than the value of the root node, and the value of all nodes in the right subtree is greater than the value of the root node (supports fast search, insertion, and deletion, with a time complexity of O(logn) and a worst-case time complexity of O(n)).
Balanced Binary Tree (AVL) : The absolute value of the height difference between the left and right subtrees is ≤1 (solves the imbalance problem of BST and ensures stable search efficiency of O(logn)).
Red-black trees maintain balance through the “red-black node” rule (insertion and deletion efficiency is higher than AVL trees, used in Java TreeMap and HashMap (JDK8)).
B-tree/B+ tree : Multi-way balanced search tree (used for database indexing, adapted to disk I/O).

Binary tree storage method

Sequential storage (array) :
- Applicable to complete binary trees, stored in level order (root node stored as index=0, left child node=2i+1, right child node=2i+2).
- Advantages: Fast node access, no need to store pointers; Disadvantages: Incomplete binary tree wastes space.
Linked storage (linked list) :
- Each node contains a “data field” + a “left pointer (pointing to the left subtree)” + a “right pointer (pointing to the right subtree)”;
- Advantages: High space utilization, suitable for any binary tree; Disadvantages: Accessing child nodes requires traversing using pointers.

The core traversal algorithm of a binary tree

The goal of traversal is to visit all nodes in the tree in a certain order, which is divided into depth-first search (DFS) and breadth-first search (BFS) .

1. Depth-first search (DFS)

(1) Preorder traversal (root → left → right)

# Recursive  Implementation
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Iterative Implementation (Stack)
def preorder_iter(root):
    stack, res = [root] if root else [], []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:  # Right subtree first on stack (stack first in, stack last out)
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

(2) Inorder traversal (left → root → right)

The inorder traversal of a binary search tree is an ascending sequence (a core characteristic).

# Recursive implementation
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Iterative Implementation (Stack)
def inorder_iter(root):
    stack, res, curr = [], [], root
    while stack or curr:
        while curr:  # Bottom of the left subtree
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        res.append(curr.val)
        curr = curr.right  # Accessing the right subtree
    return res

(3) Post-order traversal (left → right → root)

# Recursive implementation
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Iterative implementation (stack+tag)
def postorder_iter(root):
    stack, res = [(root, False)] if root else [], []
    while stack:
        node, visited = stack.pop()
        if visited:
            res.append(node.val)
        else:
            stack.append((node, True))  # Mark the root node for subsequent processing
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return res

2. Breadth-first search (BFS, level-order traversal)

Accessing nodes by “layer” (from top to bottom, from left to right) can be achieved using a queue .

from collections import deque

def levelorder(root):
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        level_size = len(queue)  # Number of nodes in the current layer
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level)  # Store results by layer
    return res

Typical application scenarios of trees

Data retrieval : Binary search tree, balanced binary tree, B+ tree (database index);
Sorting : Inorder traversal (ascending order) of a binary search tree;
Hierarchical data storage : file system, organizational chart;
String processing : Trie trees (prefix matching, such as search engine autocomplete);
Algorithm optimization : Huffman tree (data compression), decision tree (machine learning).