{"id":6999,"date":"2025-06-07T00:01:11","date_gmt":"2025-06-07T07:01:11","guid":{"rendered":"https:\/\/c-for-dummies.com\/blog\/?p=6999"},"modified":"2025-06-14T09:21:16","modified_gmt":"2025-06-14T16:21:16","slug":"climbing-the-binary-tree","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=6999","title":{"rendered":"Climbing the Binary Tree"},"content":{"rendered":"

A binary search tree works best when code is available to search the tree. Before doing so, I’d like to demonstrate how a tree is processed, one node at a time.
\n
\nContinuing from last week’s Lesson<\/a>, to visit each node in the tree you must traverse the tree, plumbing its depths. I call this function traverse()<\/em>:<\/p>\n

\r\n\/* traverse the tree *\/<\/span>\r\nvoid traverse(struct node *r)\r\n{\r\n    \/* stop on NULL, empty node *\/<\/span>\r\n    if( r==NULL )\r\n        return;\r\n\r\n    \/* fetch data *\/<\/span>\r\n    printf(\"%d\\n\",r->key);\r\n    \/* go deeper! *\/<\/span>\r\n    traverse(r->right);\r\n    traverse(r->left);\r\n}<\/pre>\n
As with the add_node()<\/em> function, traverse()<\/em> is recursive. When a NULL node is encountered, indicating an empty item, the function returns. Otherwise, it fetches a key value from the node and then traverses first the right branches and then the left branches in the tree. Eventually, all values are output, though in a manner that dominates the right branches (because the right node is inspected first).<\/p>\n
50
\n85
\n96
\n59
\n68
\n20
\n41
\n16
\n3<\/code><\/p>\n
Compare this output with the way the data is stored internally, which is illustrated in Figure 1. You can see how the output favors climbing down the right branches first.<\/p>\n
\"\"
Figure 1. A Binary Search Tree.<\/p><\/div>\n
If you change the order of the traverse()<\/em> recursive call, putting the traverse(r->left)<\/code> statement first, the output appears in a different order. Regardless, these functions are used more properly to search for data than to output an accurate representation of the tree.<\/p>\n
The second improvement to the original code I promised is to free the allocated nodes before the program quits. As with all a program’s allocated storage, nodes are freed automatically when the program ends. Still, C coders are persnickety (as they should be) with regards to freeing memory.<\/p>\n
To de-allocate the binary search tree’s storage, I added the free_tree()<\/em> function to the sample code:<\/p>\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}<\/pre>\n
The next task is to search the tree for a specific tidbit of data. I present this addition to the code in next week’s Lesson<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
The beauty of the binary search tree is how quickly you can fetch its data. 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-6999","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\/6999","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=6999"}],"version-history":[{"count":7,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6999\/revisions"}],"predecessor-version":[{"id":7035,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6999\/revisions\/7035"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6999"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6999"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6999"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
As you may suspect, this function is also recursive. It seeks the bottom-most (top-most?) node in the tree and frees it, free(r)<\/code>. This function is added to the end of the main()<\/em> function and is available on GitHub here<\/a>.<\/p>\n
Here’s sample output from the updated code<\/a>, available on GitHub:<\/p>\n