Exploring Time Complexity of Tree Operations

In this article, we'll explore the time complexity of common tree operations (traversal and insertion) to understand their performance characteristics better.

Traversal

Traversing a tree involves visiting each node in the tree.

Here is the source code for the preorder traversal of a tree:

def preorder_traversal(self, node, traversal=[]):
    # if no nodes are left,
    # end the recursion
    if not node:
        return traversal
 
    traversal.append(node.data)
 
    for child in node.children:
        # recursively traverse child nodes
        self.preorder_traversal(child, traversal)

    return traversal

void preorder_traversal(TreeNode<T>* node, vector<T>& traversal) {
    if(!node) return;
    traversal.push_back(node->data);

    for(const auto& child: node->children) {
        // Recursively traverse child nodes
        preorder_traversal(child, traversal);
    }
}

The total time required to traverse the tree is proportional to the number of nodes. If the tree contains n nodes, the time complexity is O(n).

This applies to all three types of traversal — inorder, preorder, and postorder traversal — as each method visits every node in the tree exactly once.

Insertion

Insertion involves adding a new node to the tree.

def add_child(self, child):
    self.children.append(child)

void add_child(TreeNode<T>* new_child) {
    children.push_back(new_child);
}

To insert a child to a node, we append the node to the array. Appending is a constant time operation, so the time complexity is O(1).

Summary