Binary Tree Basics

• Root node: the node located at the top level of a binary tree, with no parent node.
• Leaf node: a node with no child nodes, whose two pointers both point to None.
• Edge: a line segment connecting two nodes, i.e., a node reference (pointer).
• The level of a node: increases from top to bottom; the root node is at level 1.
• The degree of a node: the number of its child nodes. In a binary tree, the degree is 0, 1, or 2.
• The height of a binary tree: the number of edges from the root node to the farthest leaf node.
• The depth of a node: the number of edges from the root node to that node.
• The height of a node: the number of edges from the farthest leaf node to that node.

Example of inserting and deleting a node:

TreeNode P = new TreeNode(0);
// Insert node P between n1 and n2
n1.left = P;
P.left = n2;
// Delete node P
n1.left = n2;

Types of Binary Trees

Complete binary tree: only the bottom level of nodes may be unfilled, and the bottom-level nodes are filled as far left as possible.

Full binary tree: apart from leaf nodes, every node has two child nodes.

Balanced binary tree: for any node in the tree, the absolute difference between the heights of its left and right subtrees does not exceed 1.

Level-Order Traversal

Level-order traversal is essentially breadth-first traversal, also called breadth-first search (BFS).

/* Level-order traversal */
List<Integer> levelOrder(TreeNode root) {
    // Initialize a queue and add the root node
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // Initialize a list to store the traversal sequence
    List<Integer> list = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // dequeue
        list.add(node.val); // save node value
        if (node.left != null)
          queue.offer(node.left); // enqueue left child
        if (node.right != null)
          queue.offer(node.right); // enqueue right child
    }
    return list;
}

Time complexity is O(n): every node is visited once, where n is the number of nodes.

Space complexity is O(n): in the worst case, i.e., a full binary tree, just before traversing the bottom level, the queue holds at most (n+1)/2 nodes.

Preorder, inorder, and postorder traversals belong to depth-first traversal.

/* Preorder traversal */
void preOrder(TreeNode root) {
    if (root == null)
        return;
    // Visit priority: root -> left subtree -> right subtree
    list.add(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

/* Inorder traversal */
void inOrder(TreeNode root) {
    if (root == null)
        return;
    // Visit priority: left subtree -> root -> right subtree
}

/* Postorder traversal */
void postOrder(TreeNode root) {
    if (root == null)
        return;
    // Visit priority: left subtree -> right subtree -> root
}

Array Representation of Binary Trees

Representing a binary tree as an array has the following advantages:

• Array storage lies in contiguous memory, so it is cache-friendly and fast to access and traverse.
• No pointers need to be stored, which saves space.
• Nodes can be accessed at random.

However, the array representation also has limitations.

• Array storage requires contiguous memory, so it is unsuitable for trees holding very large amounts of data.
• Inserting and deleting nodes must be implemented through array insertion and deletion, which is less efficient.
• When the binary tree contains many None values, the array holds many unused node slots, so space utilization is low.

Binary Search Tree

Like the binary search algorithm, each step of a binary search tree search eliminates half of the remaining cases. The number of loop iterations is at most the height of the binary tree; when the tree is balanced, the time is O(log n).

/* Find a node */
TreeNode search(int num) {
    TreeNode cur = root;
    // Loop to search, exit after passing a leaf node
    while (cur != null) {
        // Target node is in the right subtree of cur
        if (cur.val < num)
          cur = cur.right;
        // Target node is in the left subtree of cur
        else if (cur.val > num)
          cur = cur.left;
        // Target node found, exit loop
        else
          break;
    }
    // Return the target node
    return cur;
}

• A binary search tree does not allow duplicate nodes, otherwise its definition is violated. Therefore, if the node to insert already exists in the tree, no insertion is performed and the function returns directly.
• To insert a node, we need to use a node pre to save the parent of the node visited in the previous loop iteration. This way, when traversal reaches None, we can obtain the parent node and complete the insertion.

/* Insert a node */
void insert(int num) {
    // If the tree is empty, initialize the root node
    if (root == null) {
        root = new TreeNode(num);
        return;
    }
    TreeNode cur = root, pre = null;
    // Loop to search, exit after passing a leaf node
    while (cur != null) {
        // Duplicate node found, return directly
        if (cur.val == num)
          return;
        pre = cur;
        // Insertion position is in the right subtree of cur
        if (cur.val < num)
          cur = cur.right;
        // Insertion position is in the left subtree of cur
        else
          cur = cur.left;
    }
    // Insert node
    TreeNode node = new TreeNode(num);
    if (pre.val < num)
        pre.right = node;
    else
        pre.left = node;
}

Deleting a Node:

When the degree of the node to delete is 0, the node is a leaf node and can be deleted directly.

When the degree of the node to delete is 1, replace the node to delete with its child node.

When the degree of the node to delete is 2, we cannot delete it directly and must use a node to replace it. Since the binary search tree must keep the property that the "left subtree < root < right subtree", this node can be either the smallest node in the right subtree or the largest node in the left subtree.

/* Delete a node */
void remove(int num) {
    // If the tree is empty, return early
    if (root == null)
        return;
    TreeNode cur = root, pre = null;
    // Loop to search, exit after passing a leaf node
    while (cur != null) {
        // Node to delete found, exit loop
        if (cur.val == num)
          break;
        pre = cur;
        // Node to delete is in the right subtree of cur
        if (cur.val < num)
          cur = cur.right;
        // Node to delete is in the left subtree of cur
        else
          cur = cur.left;
    }
    // If there is no node to delete, return directly
    if (cur == null)
        return;
    // Number of child nodes = 0 or 1
    if (cur.left == null || cur.right == null) {
        // When number of child nodes = 0 / 1, child = null / that child node
        TreeNode child = cur.left != null ? cur.left : cur.right;
        // Delete node cur
        if (cur != root) {
          if (pre.left == cur)
            pre.left = child;
          else
            pre.right = child;
        } else {
          // If the node to delete is the root node, reassign the root node
          root = child;
        }
    }
    // Number of child nodes = 2
    else {
        // Get the next node of cur in inorder traversal
        TreeNode tmp = cur.right;
        while (tmp.left != null) {
          tmp = tmp.left;
        }
        // Recursively delete node tmp
        remove(tmp.val);
        // Use tmp to overwrite cur
        cur.val = tmp.val;

An inorder traversal sequence of a binary search tree is ascending.

Hash Tables

Time complexity of insert, query, update, and delete in a hash table is O(1).

/* Initialize a hash table */
Map<Integer, String> map = new HashMap<>();

/* Add operations */
// Add key-value pairs (key, value) to the hash table
map.put(12836, "Xiao Ha");
map.put(15937, "Xiao Luo");
map.put(16750, "Xiao Suan");
map.put(13276, "Xiao Fa");
map.put(10583, "Xiao Ya");

/* Query operations */
// Input key into the hash table, get value
String name = map.get(15937);

/* Delete operations */
// Delete key-value pair (key, value) from the hash table
map.remove(10583);

Hash collision: multiple inputs may map to the same output.

Separate chaining converts each single element into a linked list, treating key-value pairs as list nodes, and stores all colliding key-value pairs in the same linked list.

Based on separate chaining, the hash table operations change as follows.

Query element: input key, use the hash function to get the bucket index, then access the list head node, and traverse the list, comparing key to find the target key-value pair.

Add element: first access the list head node via the hash function, then add the node (key-value pair) to the list.

Delete element: based on the hash function result, access the list head, then traverse the list to find and delete the target node.

Separate chaining has the following limitations.

Increased space usage: the list contains node pointers, which consume more memory than arrays.

Reduced query efficiency: a linear traversal of the list is needed to find the corresponding element.

The following implementation gives a simple version of a chained hash table. It uses a dynamic array instead of linked lists to simplify the code, so the hash table consists of multiple buckets, each of which is a list. It includes a hash table expansion method: when the load factor exceeds 2/3, the hash table is expanded to twice its original size.

Open addressing does not introduce extra data structures; instead, it handles hash collisions through "multiple probing."

Linear probing uses a fixed-step linear search for probing, with operations different from the ordinary hash table.

Insert element: compute the bucket index via the hash function; if the bucket already contains an element, linearly traverse backward from the collision position (step size is usually 1) until an empty bucket is found, then insert the element there.

Find element: if a hash collision occurs, use the same step size to search backward linearly until the corresponding element is found and return value; if an empty bucket is encountered, the target element is not in the hash table, so return None.

Figure 6-6 shows the key-value pair distribution of a hash table with open addressing (linear probing). According to this hash function, the last two identical key values are mapped to the same bucket. Through linear probing, they are stored in that bucket and the buckets below it in sequence.

However, linear probing is prone to "clustering". The longer the consecutive runs of occupied array positions, the more likely a hash collision occurs at those positions, which further causes those runs to grow, forming a vicious cycle and ultimately degrading the efficiency of add, delete, query, and update operations. To solve this problem, we can adopt a lazy deletion mechanism: instead of directly removing elements from the hash table, it marks the bucket using a constant TOMBSTONE. However, lazy deletion may degrade hash table performance, because each deletion produces a deletion marker, and as TOMBSTONE accumulates, search time also increases, since linear probing may need to skip many TOMBSTONE markers before finding the target element.

Graphs

Adjacency matrix and adjacency list: an adjacency list uses (adjacency list) n linked lists to represent the graph, where linked list nodes represent vertices. The i-th linked list corresponds to vertex i, which stores all its adjacent vertices (vertices connected to it).

Add or delete an edge: directly modify the specified edge in the adjacency matrix, using O(1) time. Since the graph is undirected, both directions of the edge must be updated.

Add a vertex: append a row and a column at the end of the adjacency matrix, filling them all with 0, using O(n) time.

Delete a vertex: delete one row and one column from the adjacency matrix. In the worst case, when deleting the first row and first column, (n−1)² elements must be "shifted up-left," using O(n²) time.

Initialize: pass in n vertices, initialize a vertex list vertices of length n, using O(n) time; initialize an n×n adjacency matrix adjMat, using O(n²) time.

Add an edge: append the edge at the end of the linked list corresponding to the vertex, using O(1) time. Since the graph is undirected, both directions of the edge must be added.

Delete an edge: find and delete the specified edge in the linked list corresponding to the vertex, using O(m) time. In an undirected graph, both directions of the edge must be deleted at the same time.

Add a vertex: add a linked list to the adjacency list, and set the newly added vertex as the linked list head node, using O(1) time.

Delete a vertex: traverse the entire adjacency list, delete all edges containing the specified vertex, using O(n+m) time.

Initialize: create n vertices and 2m edges in the adjacency list, using O(n+m) time.

Breadth-first traversal

Time complexity: all vertices are enqueued and dequeued once, using O(|V|) time; when traversing the adjacent vertices of each vertex, since it is an undirected graph, every edge is accessed 2 times, using O(2|E|) time; overall O(|V|+|E|).

Space complexity: the list res, the hash set visited, and the queue que hold at most |V| vertices, using O(|V|) space.

Depth-first traversal

Time complexity: all vertices are visited once, using O(|V|) time; all edges are visited 2 times, using O(2|E|) time; overall O(|V|+|E|).

Space complexity: the list res, the hash set visited hold at most |V| vertices, and the maximum recursion depth is |V|, so O(|V|) space is used.

/* Breadth-first traversal */
// Use an adjacency list to represent the graph, so that all adjacent vertices of a given vertex can be obtained
List<Vertex> graphBFS(GraphAdjList graph, Vertex startVet) {
    // Vertex traversal sequence
    List<Vertex> res = new ArrayList<>();
    // Hash set, used to record visited vertices
    Set<Vertex> visited = new HashSet<>();
    visited.add(startVet);
    // Queue used to implement BFS
    Queue<Vertex> que = new LinkedList<>();
    que.offer(startVet);
    // Starting from vertex vet, loop until all vertices are visited
    while (!que.isEmpty()) {
        Vertex vet = que.poll(); // dequeue the front vertex
        res.add(vet); // record visited vertex
        // Traverse all adjacent vertices of this vertex
        for (Vertex adjVet : graph.adjList.get(vet)) {
            if (visited.contains(adjVet))
                continue; // skip already visited vertices
            que.offer(adjVet); // only enqueue unvisited vertices
            visited.add(adjVet); // mark this vertex as visited
        }
    }
    // Return vertex traversal sequence
    return res;
}

/* Helper function for depth-first traversal */
void dfs(GraphAdjList graph, Set<Vertex> visited, List<Vertex> res, Vertex vet) {
    res.add(vet); // record visited vertex
    visited.add(vet); // mark this vertex as visited
    // Traverse all adjacent vertices of this vertex
    for (Vertex adjVet : graph.adjList.get(vet)) {
        if (visited.contains(adjVet))
          continue; // skip already visited vertices
        // Recursively visit adjacent vertices
        dfs(graph, visited, res, adjVet);
    }
}

/* Depth-first traversal */
// Use an adjacency list to represent the graph, so that all adjacent vertices of a given vertex can be obtained
List<Vertex> graphDFS(GraphAdjList graph, Vertex startVet) {
    // Vertex traversal sequence
    List<Vertex> res = new ArrayList<>();
    // Hash set, used to record visited vertices
    Set<Vertex> visited = new HashSet<>();
    dfs(graph, visited, res, startVet);
    return res;
}