Exploring Time Complexity of Binary Tree Operations

This article is a complementary resource to the DSA with Python and DSA with C++ courses.

Exploring Time Complexity of Binary Tree Operations

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

Traversal

Traversing a binary tree involves visiting each node in the tree. Here is the source code for inorder traversal in a binary tree.

Python

Java

C++

def inorder_traversal(self, node, visited_nodes=[]):
    if node is not None:
        # Traverse the left child
        self.inorder_traversal(node.left, visited_nodes)
        visited_nodes.append(node.data)
        # Traverse the right child
        self.inorder_traversal(node.right, visited_nodes)
    return visited_nodes

void inorder_traversal(BinaryTreeNode<T>* node, vector<T>& traversal) {
    if (!node) return;
    // Traverse the left child
    inorder_traversal(node->left, traversal);
    traversal.push_back(node->data);
    // Traverse the right child    
    inorder_traversal(node->right, traversal);
}

The total time required to traverse the tree is proportional to the number of nodes. If there are 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. To insert a child to a node, we assign the new node either to the right or left of the node.

Python

Java

C++

def add_left_child(self, node):
    self.left = node
 
def add_right_child(self, node):
    self.right = node

void add_left_child(BinaryTreeNode<T>* node) {
    left = node;
}
 
void add_right_child(BinaryTreeNode<T>* node) {
    right = node;
}

Assigning a node is a constant time operation, so the time complexity is O(1).

Summary

Operation	Time Complexity
Traversal	`O(n)`
Insertion	`O(1)`