{"id":7015,"date":"2025-06-14T00:01:35","date_gmt":"2025-06-14T07:01:35","guid":{"rendered":"https:\/\/c-for-dummies.com\/blog\/?p=7015"},"modified":"2025-06-07T11:43:41","modified_gmt":"2025-06-07T18:43:41","slug":"searching-a-binary-tree","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=7015","title":{"rendered":"Searching a Binary Tree"},"content":{"rendered":"

As you might suspect, searching a binary search tree (BST) involves a recursive function. This function must plow through the tree, finding a value in a specific node. Because the BST is organized, the search process works far more quickly than when the data is unorganized or set in a sequential array. In fact, the bsearch()<\/em> function<\/a> uses a similar scheme requiring that the data first be sorted before the function works its magic.
\n
\nContinuing from last week’s Lesson<\/a>, I’ve replaced the traverse()<\/em> function with a search()<\/em> function. Its arguments are a node pointer and the value to look for:<\/p>\n

\r\n\/* search for a value *\/<\/span>\r\nstruct node *search(struct node *r, int v)\r\n{\r\n    \/* return on empty or when key found *\/<\/span>\r\n    if( r==NULL || r->key == v )\r\n        return(r);\r\n\r\n    \/* search for values less *\/<\/span>\r\n    if( v < r->key )\r\n        return( search( r->left,v ) );\r\n    \/* search for values greater *\/<\/span>\r\n    return( search(r->right,v ) );\r\n}<\/pre>\n
The first if<\/em> test is for both the NULL pointer and the proper value. When the NULL pointer is encountered, the search has reached the end of a branch (or whatever the proper term is). When the key value is found, the search is over. At either point, recursion unwinds, returning the value of either NULL (failure) or the desired node (success).<\/p>\n
The second if<\/em> test plumbs the left node when the search value is less than the current node’s key value. The search is performed within the return<\/em> statement, which is how the proper result — NULL or the found node — is returned to the calling statement.<\/p>\n
When the value of the current node is greater than the current’s node’s key value, the search goes to the right node. The result is returned directly (that recursion thing).<\/p>\n
The calling statement examines the returned result, either NULL for a failed search or the address of the node containing the matching key value.<\/p>\n
Here is the full code:<\/p>\n
2025_06_14-Lesson.c<\/a><\/h3>\n
\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <time.h>\r\n\r\nstruct node {\r\n    int key;\r\n    struct node *left;\r\n    struct node *right;\r\n};\r\n\r\n\/* search for a value *\/<\/span>\r\nstruct node *search(struct node *r, int v)\r\n{\r\n    \/* return on empty or when key found *\/<\/span>\r\n    if( r==NULL || r->key == v )\r\n        return(r);\r\n\r\n    \/* search for values less *\/<\/span>\r\n    if( v < r->key )\r\n        return( search( r->left,v ) );\r\n    \/* search for values greater *\/<\/span>\r\n    return( search(r->right,v ) );\r\n}\r\n\r\n\/* free the tree's node storage *\/<\/span>\r\nvoid free_tree(struct node *r)\r\n{\r\n    \/* stop on NULL *\/<\/span>\r\n    if( r==NULL )\r\n        return;\r\n\r\n    \/* plumb the depths *\/<\/span>\r\n    free_tree(r->left);\r\n    free_tree(r->right);\r\n    free(r);        \/* the (current) bottom node *\/<\/span>\r\n}\r\n\r\n\/* add a new node *\/<\/span>\r\nstruct node *add_node(struct node *r,int k)\r\n{\r\n\r\n    if( r==NULL )\r\n    \/* allocate a new node *\/<\/span>\r\n    {\r\n        r = malloc( sizeof(struct node) );\r\n        if( r==NULL )\r\n        {\r\n            fprintf(stderr,\"Unable to allocate memory\\n\");\r\n            exit(1);\r\n        }\r\n        r->key = k;        \/* set its key *\/<\/span>\r\n        r->right = NULL;\r\n        r->left = NULL;\r\n    }\r\n    else\r\n    {\r\n        \/* smaller values go on the left *\/<\/span>\r\n        if( k < r->key )\r\n            r->left = add_node(r->left,k);\r\n        \/* larger values go on the right *\/<\/span>\r\n        else\r\n            r->right = add_node(r->right,k);\r\n    }\r\n    return(r);\r\n}\r\n\r\nint main()\r\n{\r\n    static int count = 9;\r\n    int data[] = {\r\n        50, 20, 85, 16, 41, 59, 96, 3, 68\r\n    };\r\n    struct node *root = NULL;\r\n    struct node *result;\r\n    int x,value;\r\n\r\n    \/* construct the tree *\/<\/span>\r\n    for( x=0; x<count; x++ )\r\n        root = add_node(root,data[x]);\r\n\r\n    \/* search the tree *\/<\/span>\r\n    printf(\"Locate value: \");\r\n    scanf(\"%d\",&value);\r\n    result = search(root,value);\r\n    if( result!=NULL )\r\n        printf(\"Value %d found\\n\",value);\r\n    else\r\n        printf(\"Value %d not found\\n\",value);\r\n\r\n    \/* clean-up *\/<\/span>\r\n    free_tree(root);\r\n    return 0;\r\n}<\/pre>\n
Obviously, more can be done with a Binary Search Tree beyond looking up simple values. The hurdle to clear from demonstration purposes is loading the tree with values.<\/p>\n
For example, I could set all kinds of interesting data to search, but with the data already written in the code it seems silly to then search for what’s already known. Even so, binary search trees represent an excellent way to organize and locate data. You find this type of structure implemented often in programming, which is why being familiar with its operation and coding is important to know.<\/p>\n","protected":false},"excerpt":{"rendered":"
The point of a binary search tree is to be able to search for data in the tree. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-7015","post","type-post","status-publish","format-standard","hentry","category-main"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/7015","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=7015"}],"version-history":[{"count":3,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/7015\/revisions"}],"predecessor-version":[{"id":7027,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/7015\/revisions\/7027"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=7015"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=7015"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=7015"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}