{"id":4797,"date":"2015-02-23T10:45:52","date_gmt":"2015-02-23T18:45:52","guid":{"rendered":"https:\/\/blog.digilentinc.com\/?p=4797"},"modified":"2025-06-02T03:40:27","modified_gmt":"2025-06-02T10:40:27","slug":"binary-search-trees","status":"publish","type":"post","link":"https:\/\/digilent.com\/blog\/binary-search-trees\/","title":{"rendered":"Binary Search Trees: Functions & Insertion Explained"},"content":{"rendered":"

The binary search tree (BST) is a data structure that is much different from the other structures that we’ve gone over so far. Unlike stacks, queues, and lists, a BST’s struct is not a “straight-line”. Each node in a BST has a left and right child node.<\/p>\n

\"A<\/a>
A binary search tree.<\/figcaption><\/figure>\n

 <\/p>\n

The BST above is a classic example of how BSTs work. “10” is the first node in the tree, and then all the other nodes are put in the tree. We’re going to make an unbalanced search tree today, and with the exception of deleting nodes, the location of nodes won’t change. A balanced search tree, which we won’t go over today, moves nodes around in tree to keep balance.<\/p>\n

 <\/p>\n

There are four main functions of a BST:
\n1. Insert. Due to the nature of BSTs, the insert function will create a new leaf<\/em> (a bottom node of the tree).
\n2. Find functions (findMin, findMax, and contains). The find function\u00a0is very similar to insert\u00a0and\u00a0will go down the tree until the value is found.
\n3. Remove. Remove deletes a node. This is most complicated function in a BST, as there are three different cases (we will go over these).
\n4. Print. There are three ways to print a BSTs that we will go over in this post. Each one prints the nodes out in a different order.
\nWhat makes a binary search tree so interesting is that the insert, find, and delete functions all have an average complexity of O(log n). When those functions are called, each iteration will reduce the number of “n” values that are left to search through by half, leading to O(log n) complexity. An easy example is search, where if we search for “14” in the BST above, the first iteration will take us to 11, removing the entire left half of the BST.
\nNow that BSTs have been introduced, let’s get into their implementation. It’s important to note that our BST won’t support duplicates, but that is definitely a feature you can add! We won’t go over the main and header files, most they are pretty close to the same as in the stacks and queues blog post. Check them out here: header<\/strong><\/a> and main<\/strong><\/a>.<\/p>\n

 <\/p>\n

1. Insert<\/p>\n

\"Insert<\/a>
Insert into tree.<\/figcaption><\/figure>\n

You can see there are two insert functions. The first function is just calling the second function. This may seem a little confusing, but due to recursive calls, this makes it easier to call in main.<\/p>\n

 <\/p>\n

In insert, there are four cases. The first is our base case, we create a new node, assign the element value to our entry, then assign the left and right nodes to NULL. Our second and third cases are our recursive calls, these two move the the element farther down the tree. If the element is less than the value in the current branch, we send it left, but otherwise we’ll send it right. These two statements are what make BSTs interesting. Other data structures’ insert functions are linear, but the BST’s insert has multiple options.<\/p>\n

 <\/p>\n

2. findMin, findMax, and contains<\/p>\n

\"Search<\/a>
Search functions.<\/figcaption><\/figure>\n

 <\/p>\n

These functions are all very similar, but each has a\u00a0different purpose. Contains is a boolean function, and it goes through the tree\u00a0to\u00a0return “true” if the value is found. Functions findMin and findMax are essential “mirrored” functions. FindMin goes to the left node of each branch until the last left node is reached — this is the smallest value– and then this node is returned. FindMax goes through all the right nodes until the end is reached, then returns the largest value node.<\/p>\n

 <\/p>\n

3. Remove<\/p>\n

\"Remove<\/a>
Remove from tree.<\/figcaption><\/figure>\n

 <\/p>\n

Remove is easily the most complicated function of a Binary Search Tree. There are three separate cases for remove.
\nThe first is when the node to be removed has no children. This is the easiest case, wherein we just delete the node.
\nThe second case is when the node to be removed has one child. This case isn’t extremely difficult either, as we assign the child of the node to be removed to the original node’s location and then delete the old node. The last case is easily the most complicated, when the node has two children. In order for us to ensure the integrity of our BST, we must replace the node to be removed with a value that doesn’t how the binary search tree works. For us to do this, we need to pick the smallest node on the right child’s subtree. This is the only node that will ensure that the tree’s integrity isn’t changed. Here is where our findMin function is useful, we call findMin on the right node, and assign that value to the node to be deleted. We then “move” the node we found to the location of the node to be deleted, then we update the tree accordingly (as duplicates aren’t allowed).<\/p>\n

 <\/p>\n

4. Print Functions<\/p>\n

\"newprint\"<\/a><\/p>\n

 <\/p>\n

Binary Search Trees can be printed out in three ways: PreOrder, PostOrder, and InOrder. All these functions have a “cout” call and two recursive calls, that is basically all that the print functions are.<\/p>\n

 <\/p>\n

PreOrder prints out the value of node before calling node->left and node->right. This prints out the left side of a tree, then the right side of the tree.<\/p>\n

 <\/p>\n

PostOrder prints out the values of node->left and node->right, then prints out the value of the node. Because this is a recursive call, it will print out all the leaf nodes, and then print out the branches.<\/p>\n

 <\/p>\n

InOrder is fairly\u00a0simple. By printing out the node value in between calling the node->left and node->right, we print out the tree in order.<\/p>\n

0<\/span><\/a><\/div><\/div>
Be the 1st to vote.<\/div><\/div>
<\/div>","protected":false},"excerpt":{"rendered":"

The binary search tree (BST) is a data structure that is much different from the other structures that we’ve gone over so far. Unlike stacks, queues, and lists, a BST’s struct is not a “straight-line”. Each node in a BST has a left and right child node.<\/p>\n","protected":false},"author":29,"featured_media":4970,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1563],"tags":[],"ppma_author":[4478],"class_list":["post-4797","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-guide"],"jetpack_featured_media_url":"https:\/\/digilent.com\/blog\/wp-content\/uploads\/2015\/01\/tree.png","authors":[{"term_id":4478,"user_id":29,"is_guest":0,"slug":"josh-woldstad","display_name":"Josh","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/b4b62729a3daba9bb76117db7130e81e?s=96&d=mm&r=g","author_category":"","user_url":"","last_name":"Woldstad","last_name_2":"","first_name":"Josh","first_name_2":"","job_title":"","description":"I love Coding!"}],"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/posts\/4797","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/users\/29"}],"replies":[{"embeddable":true,"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/comments?post=4797"}],"version-history":[{"count":3,"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/posts\/4797\/revisions"}],"predecessor-version":[{"id":31615,"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/posts\/4797\/revisions\/31615"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/media\/4970"}],"wp:attachment":[{"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/media?parent=4797"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/categories?post=4797"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/tags?post=4797"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/digilent.com\/blog\/wp-json\/wp\/v2\/ppma_author?post=4797"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}