How to Search a Binary Tree in Objective-C

Submitted by matt_eaton on Mon, 11/26/2018 - 03:03 AM

Tags

Objective-C

How to Search a Binary Tree in Objective-C

In a recent tutorial I described how to create a binary tree data structure and populate it with numerical data. Now, in this tutorial, I will explain how to search each level of the binary tree for a specific numeric value. As previously described in my past tutorial, search and sort operations on binary tree's is a very popular use case because of the efficiency in performing these operations. For a binary tree with n elements the time complexity in searching the tree is O(log(n)) in the worst case. Where log is of base 2 and n is the number of elements in the tree. This means that every node in the tree does not have to be evaluated in order for the node to be found. In the worst case, half of the nodes would.

NOTE: This tutorial builds on a previous tutorial that creates the binary tree data structure. This tutorial does require reading the previous tutorial first and some fundamental knowledge of how Objective-c works as well as some basic computer science algorithm concepts.

Searching a Binary Tree in Objective-C 🚀

Building upon the previous knowledge of creating the binary tree, let's now take a look at how to search the tree for a specific numerical value. Starting with the find: method below, this method recursively passes a value (the number to find) at a level (the tree level) in a tree node. This method call's itself until one of two things happen; either the num contained on the node is equated to the value in the find method, or the bottom of the tree has reached and -1 is returned for the level. In the case where the bottom of the tree is reached, this means that the node about to be evaluated is NULL. The node is NULL because no value was ever tied to it when the parent node was created. NULL was the default value.

Notice that each time the value is not equated that the num and value are evaluated to see if the value is lesser than or greater than the num on the referenced node. If the value is lesser-than, the level is incremented and the left side is traversed. If the value is greater-than, the level is incremented the right side is traversed. Once the value and num have been equated the level is returned to tell the searching method which level of the tree the value was found at.

- (int) find:(int)value atLevel:(int)level onTree:(Node *)tree {
    // Complexities of searching a binary tree.
    // Time complexity: O(log(n))
    // Space complexity: O(log(n)
    int levelValue = level;
    if (tree == NULL) {
        return -1;
    } else {
 
        if (value == tree.num) {
            return levelValue;
        } else {
            if (value < tree.num) {
                levelValue = [self find:value atLevel: ++level onTree:tree.left];
            } else {
                levelValue = [self find:value atLevel: ++level onTree:tree.right];
            }
        }
    }
    return levelValue;
}

In Summary ⌛️

In summary I hope that this tutorial provides valuable information on how to search a binary tree in Objective-C. Swift has a very similar implementation except the for the node values are not being passed around as a pointer. I hope you enjoyed this tutorial and if you have any questions, comments, or concerns, please leave a comment below and I will make sure to address it as soon as I am able to. Thank you very much for reading and the code from this tutorial can be downloaded from my Github here.

CREDITS: COVER IMAGE DESIGNED BY FREEPIK.

Member for

3 years 9 months

Matt Eaton

Long time mobile team lead with a love for network engineering, security, IoT, oss, writing, wireless, and mobile. Avid runner and determined health nut living in the greater Chicagoland area.

Twitter

Github