SearchāŒ˜ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in C++

Binary Tree Operations

Explore how to perform and implement binary tree operations such as searching, insertion, and deletion using C++. Learn to apply depth-first and level-order traversals to manage and maintain tree structure. Understand the time and space complexity implications of these operations to handle hierarchical data efficiently.

We'll cover the following...

Binary trees store data in a hierarchical structure. Unlike binary search trees (BSTs), they do not follow any ordering rules, so we cannot directly determine where to go when searching or inserting.

Because of this, most operations rely on traversing the tree.

In this lesson, we study three fundamental operations:

  • Searching

  • Insertion

  • Deletion

Searching in a binary tree

Searching in a binary tree means checking whether a given value exists in the tree. As there is no ordering property, we cannot skip parts of the tree. In the worst case, we may need to visit every node.

A common approach is to use depth-first search (DFS). We start at the root, check its value, and if it does not match, we recursively search the left subtree and then the right subtree.

How this algorithm works

  1. Start at the root node.

  2. If the current node is nullptr, return False because the value is not found.

  3. Check if the current nodeā€™s value matches the target:

    1. If yes, return True

  4. If not, recursively search the left subtree.

  5. If the value is not found in the left subtree, search the right subtree.

  6. Return True if the value is found in either subtree, otherwise return False.

C++ implementation

Below is the C++ implementation of search in a binary tree.

C++ 17
bool search(TreeNode* root, int target) {
    // Base case: if the current node is nullptr, the value is not found
    if (root == nullptr) {
        return false;
    }
    // Check if the current node's value matches the target
    if (root->data == target) {
        return true;
    }
    // Recursively search in the left subtree OR right subtree
    // If found in either, return true
    return search(root->left, target) ||
           search(root->right, target);
}
Search in a binary tree

Time complexity: O(n)O(n) ...