1<!doctype html><html lang=en-us><head><meta charset=utf-8><meta name=viewport content="width=device-width,initial-scale=1"><meta name=robots content="noodp"><title>Binary Search Trees - Austin Christiansen</title><meta name=Description content="Austin Christiansen's Personal Blog and Portfolio"><meta property="og:title" content="Binary Search Trees"><meta property="og:description" content><meta property="og:type" content="article"><meta property="og:url" content="https://austinchristiansen.com/posts/bst/"><meta property="article:section" content="posts"><meta property="article:published_time" content="2022-08-10T00:00:00+00:00"><meta property="article:modified_time" content="2022-08-10T00:00:00+00:00"><meta property="og:site_name" content="Austin Christiansen"><meta name=twitter:card content="summary"><meta name=twitter:title content="Binary Search Trees"><meta name=twitter:description content><meta name=application-name content="Austin Christiansen"><meta name=apple-mobile-web-app-title content="Austin Christiansen"><meta name=theme-color content="#ffffff"><meta name=msapplication-TileColor content="#da532c"><link rel="shortcut icon" type=image/x-icon href=/favicon.ico><link rel=icon type=image/png sizes=32x32 href=/favicon-32x32.png><link rel=icon type=image/png sizes=16x16 href=/favicon-16x16.png><link rel=apple-touch-icon sizes=180x180 href=/apple-touch-icon.png><link rel=mask-icon href=/safari-pinned-tab.svg color=#5bbad5><link rel=manifest href=/site.webmanifest><link rel=canonical href=https://austinchristiansen.com/posts/bst/><link rel=next href=https://austinchristiansen.com/posts/tw/><link rel=stylesheet href=/css/style.min.css><link rel=preload href=https://cdn.jsdelivr.net/npm/@fortawesome/[email protected]/css/all.min.css as=style onload='this.onload=null,this.rel="stylesheet"'><noscript><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/@fortawesome/[email protected]/css/all.min.css></noscript><link rel=preload href=https://cdn.jsdelivr.net/npm/[email protected]/animate.min.css as=style onload='this.onload=null,this.rel="stylesheet"'><noscript><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/[email protected]/animate.min.css></noscript>
1<script type=application/ld+json>{"@context":"http://schema.org","@type":"BlogPosting","headline":"Binary Search Trees","inLanguage":"en-us","mainEntityOfPage":{"@type":"WebPage","@id":"https:\/\/austinchristiansen.com\/posts\/bst\/"},"genre":"posts","wordcount":3101,"url":"https:\/\/austinchristiansen.com\/posts\/bst\/","datePublished":"2022-08-10T00:00:00+00:00","dateModified":"2022-08-10T00:00:00+00:00","publisher":{"@type":"Organization","name":""},"author":{"@type":"Person","name":"Austin Christiansen"},"description":""}</script>
1</head><body data-header-desktop=auto data-header-mobile=auto>
1<script type=text/javascript>(window.localStorage&&localStorage.getItem("theme")?localStorage.getItem("theme")==="dark":"auto"==="auto"?window.matchMedia("(prefers-color-scheme: dark)").matches:"auto"==="dark")&&document.body.setAttribute("theme","dark")</script>
1<div id=mask></div><div class=wrapper><header class=desktop id=header-desktop><div class=header-wrapper><div class=header-title><a href=/ title="Austin Christiansen">> Austin Christiansen</a></div><div class=menu><div class=menu-inner><a class=menu-item href=/>Home </a><a class=menu-item href=/posts>Posts </a><a class=menu-item href=/resume.pdf>Resume </a><span class="menu-item delimiter"></span><span class="menu-item search" id=search-desktop> 2<input type=text placeholder="Search titles or contents..." id=search-input-desktop> 3<a href=javascript:void(0); class="search-button search-toggle" id=search-toggle-desktop title=Search><i class="fas fa-search fa-fw" aria-hidden=true></i></a> 4<a href=javascript:void(0); class="search-button search-clear" id=search-clear-desktop title=Clear><i class="fas fa-times-circle fa-fw" aria-hidden=true></i></a> 5<span class="search-button search-loading" id=search-loading-desktop><i class="fas fa-spinner fa-fw fa-spin" aria-hidden=true></i></span> 6</span><a href=javascript:void(0); class="menu-item theme-switch" title="Switch Theme"><i class="fas fa-adjust fa-fw" aria-hidden=true></i></a></div></div></div></header><header class=mobile id=header-mobile><div class=header-container><div class=header-wrapper><div class=header-title><a href=/ title="Austin Christiansen">> Austin Christiansen</a></div><div class=menu-toggle id=menu-toggle-mobile><span></span><span></span><span></span></div></div><div class=menu id=menu-mobile><div class=search-wrapper><div class="search mobile" id=search-mobile><input type=text placeholder="Search titles or contents..." id=search-input-mobile> 7<a href=javascript:void(0); class="search-button search-toggle" id=search-toggle-mobile title=Search><i class="fas fa-search fa-fw" aria-hidden=true></i></a> 8<a href=javascript:void(0); class="search-button search-clear" id=search-clear-mobile title=Clear><i class="fas fa-times-circle fa-fw" aria-hidden=true></i></a> 9<span class="search-button search-loading" id=search-loading-mobile><i class="fas fa-spinner fa-fw fa-spin" aria-hidden=true></i></span></div><a href=javascript:void(0); class=search-cancel id=search-cancel-mobile>Cancel</a></div><a class=menu-item href=/ title>Home</a><a class=menu-item href=/posts title>Posts</a><a class=menu-item href=/resume.pdf title>Resume</a><a href=javascript:void(0); class="menu-item theme-switch" title="Switch Theme"> 10<i class="fas fa-adjust fa-fw" aria-hidden=true></i></a></div></div></header><div class="search-dropdown desktop"><div id=search-dropdown-desktop></div></div><div class="search-dropdown mobile"><div id=search-dropdown-mobile></div></div><main class=main><div class=container><div class=toc id=toc-auto><h2 class=toc-title>Contents</h2><div class=toc-content id=toc-content-auto></div></div><article class="page single"><h1 class="single-title animate__animated animate__flipInX">Binary Search Trees</h1><div class=post-meta><div class=post-meta-line><span class=post-author><a href=https://austinchristiansen.com title=Author target=_blank rel="noopener noreffer author" class=author><i class="fas fa-user-circle fa-fw" aria-hidden=true></i>Austin Christiansen</a></span></div><div class=post-meta-line><i class="far fa-calendar-alt fa-fw" aria-hidden=true></i> <time datetime=2022-08-10>2022-08-10</time> <i class="fas fa-pencil-alt fa-fw" aria-hidden=true></i> 3101 words 11<i class="far fa-clock fa-fw" aria-hidden=true></i> 15 minutes </div></div><div class="details toc" id=toc-static data-kept><div class="details-summary toc-title"><span>Contents</span> 12<span><i class="details-icon fas fa-angle-right" aria-hidden=true></i></span></div><div class="details-content toc-content" id=toc-content-static><nav id=TableOfContents><ul><li><ul><li><a href=#creating-a-header-only-templated-binary-search-tree-in-c>Creating a header-only templated Binary Search Tree in C++.</a><ul><li><a href=#binary-search-tree-basics>Binary Search Tree Basics</a></li><li><a href=#template-basics>Template Basics</a></li><li><a href=#defining-the-node>Defining The Node</a></li><li><a href=#binary-search-tree-basic-methods>Binary Search Tree Basic Methods</a></li><li><a href=#searching>Searching</a></li><li><a href=#insertion>Insertion</a></li><li><a href=#removal>Removal</a><ul><li><ul><li><a href=#case-1-node-has-no-children>Case 1: Node Has No Children</a></li><li><a href=#case-2-node-has-one-child>Case 2: Node Has One Child</a></li><li><a href=#case-3-node-has-two-children>Case 3: Node Has Two Children</a></li></ul></li></ul></li><li><a href=#emptying-the-tree>Emptying The Tree</a></li><li><a href=#printing-the-nodes>Printing The Nodes</a></li><li>
12<a href=#conclusion>Conclusion</a></li></ul></li></ul></li></ul></nav></div></div><div class=content id=content><h3 id=creating-a-header-only-templated-binary-search-tree-in-c>Creating a header-only templated Binary Search Tree in C++.</h3><p>In this post, we’ll explore how to make a Binary Search Tree that is compatible with a variety of data types in C++.</p><p>Â </p><p>In this post, I create a templated Binary Search Tree in C++. Templated data structures allow the programmer to use the class with any data type that can be compared with the standard comparison operators. This flexibility allows one class to be used for multiple data structures without creating an entire new data structure.</p><p>Â </p><p><a href=https://github.com/austin-mc/BinarySearch target=_blank rel="noopener noreffer">Check out the GitHub repository with the code used in this article</a></p><p>Â </p><h4 id=binary-search-tree-basics>Binary Search Tree Basics</h4><p>If you’re already familiar with Binary Search Trees, feel free to skip to the next section.</p><p>A Binary Search Tree is just a Binary Tree with a couple extra properties:</p><ol><li>All values in the left subtree are less than the value of the parent</li><li>All values in the right subtree are greater than the value of the parent</li></ol><p>Â </p><p><img class=lazyload src=/svg/loading.min.svg data-src=/images/BST.png data-srcset="/images/BST.png, /images/BST.png 1.5x, /images/BST.png 2x" data-sizes=auto alt=/images/BST.png title="Binary Search Tree Visualization"></p><p>Â </p><p>These properties make Binary Search Trees extremely useful for storing data that will need to be searched frequently. To find a value in the tree, we simply compare it to the root node. If the value of the root is greater than the value we want to find, we move left in the tree. If its less than the value we want to find, we move right.</p><h4 id=template-basics>Template Basics</h4><p>Templating in C++ is useful for creating data structures that may be used for a variety of data types. To template our class, we need to let C++ know by putting <code>template <typename T></code> or <code>template <class T></code> on the line before the class declaration and <strong>every</strong> method using a templated type. When we define a method, we’ll add a <code><T></code> to the name of the class as well. Here’s an example constructor for the BST class:</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt>1 13</span><span class=lnt>2 14</span><span class=lnt>3 15</span><span class=lnt>4 16</span><span class=lnt>5 17</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=c1>//Constructor with initial value for root 18</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 19</span></span><span class=line><span class=cl><span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>BST</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 20</span></span><span class=line><span class=cl> <span class=n>root</span> <span class=o>=</span> <span class=k>new</span> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>></span><span class=p>(</span><span class=n>data</span><span class=p>);</span> 21</span></span><span class=line><span class=cl><span class=p>}</span> 22</span></span></code></pre></td></tr></table></div></div><p>Â </p><p>Notice how our parameter for the constructor is of type <code>T</code> as well. We’ll use this through the code as a placeholder for whatever data type the BST will actually hold when its used. One last thing to keep in mind when creating a templated data structure is that they are typically created as header-only libraries. This means that the class definition and all method definitions will be contained in a single header file instead of the typical .h and .cpp file combination.</p><h4 id=defining-the-node>Defining The Node</h4><p>Now that we have the basics, lets get started on our BST. The first thing we’ll do is define our nodes. A node is a basic data structure that holds our data as well as pointers to the left and right leaf nodes. In C++, this can be done with either a struct or a class. In this example I chose to use a struct.</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 23</span><span class=lnt> 2 24</span><span class=lnt> 3 25</span><span class=lnt> 4 26</span><span class=lnt> 5 27</span><span class=lnt> 6 28</span><span class=lnt> 7 29</span><span class=lnt> 8 30</span><span class=lnt> 9 31</span><span class=lnt>10 32</span><span class=lnt>11 33</span><span class=lnt>12 34</span><span class=lnt>13 35</span><span class=lnt>14 36</span><span class=lnt>15 37</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 38</span></span><span class=line><span class=cl><span class=k>struct</span> <span class=nc>Node</span> <span class=p>{</span> 39</span></span><span class=line><span class=cl> <span class=n>T</span> <span class=n>data</span><span class=p>;</span> 40</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o>*</span> <span class=n>left</span><span class=p>;</span> 41</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o>*</span> <span class=n>right</span><span class=p>;</span> 42</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>);</span> 43</span></span><span class=line><span class=cl><span class=p>};</span> 44</span></span><span class=line><span class=cl> 45</span></span><span class=line><span class=cl><span class=c1>// Constructor 46</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 47</span></span><span class=line><span class=cl><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Node</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>){</span> 48</span></span><span class=line><span class=cl>
48 <span class=k>this</span><span class=o>-></span><span class=n>data</span> <span class=o>=</span> <span class=n>data</span><span class=p>;</span> 49</span></span><span class=line><span class=cl> <span class=k>this</span><span class=o>-></span><span class=n>left</span> <span class=o>=</span> <span class=k>nullptr</span><span class=p>;</span> 50</span></span><span class=line><span class=cl> <span class=k>this</span><span class=o>-></span><span class=n>right</span> <span class=o>=</span> <span class=k>nullptr</span><span class=p>;</span> 51</span></span><span class=line><span class=cl><span class=p>}</span> 52</span></span></code></pre></td></tr></table></div></div><p>Â </p><p>The only method in our node struct is a constructor. Don’t forget the <code>template <typename T></code> prior to the method and the <code><T></code> before the scope resolution when defining the method.</p><h4 id=binary-search-tree-basic-methods>Binary Search Tree Basic Methods</h4><p>When creating our BST, theres a few methods we’ll want to define:</p><ol><li>Constructor</li><li>Destructor</li><li>Insert</li><li>Find</li><li>Remove</li><li>Empty</li><li>Print</li></ol><p>Â </p><p>We’ll begin by declaring the class and method footprints. In this example I created public methods and private helper methods to make code cleaner when using the BST. This allows the user to call methods in a more natural way, such as <code>bst.Insert(20)</code> as opposed to <code>bst.Insert(root, 20)</code>. This is purely personal preference and these methods can be written without helpers just as easily.</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 53</span><span class=lnt> 2 54</span><span class=lnt> 3 55</span><span class=lnt> 4 56</span><span class=lnt> 5 57</span><span class=lnt> 6 58</span><span class=lnt> 7 59</span><span class=lnt> 8 60</span><span class=lnt> 9 61</span><span class=lnt>10 62</span><span class=lnt>11 63</span><span class=lnt>12 64</span><span class=lnt>13 65</span><span class=lnt>14 66</span><span class=lnt>15 67</span><span class=lnt>16 68</span><span class=lnt>17 69</span><span class=lnt>18 70</span><span class=lnt>19 71</span><span class=lnt>20 72</span><span class=lnt>21 73</span><span class=lnt>22 74</span><span class=lnt>23 75</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 76</span></span><span class=line><span class=cl><span class=k>class</span> <span class=nc>BST</span> <span class=p>{</span> 77</span></span><span class=line><span class=cl> <span class=k>public</span><span class=o>:</span> 78</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>;</span> 79</span></span><span class=line><span class=cl> 80</span></span><span class=line><span class=cl> <span class=n>BST</span><span class=p>();</span> 81</span></span><span class=line><span class=cl> <span class=n>BST</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>);</span> 82</span></span><span class=line><span class=cl> <span class=o>~</span><span class=n>BST</span><span class=p>();</span> 83</span></span><span class=line><span class=cl> 84</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>Insert</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>);</span> 85</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>Find</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>);</span> 86</span></span><span class=line><span class=cl>
86 <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>Remove</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>);</span> 87</span></span><span class=line><span class=cl> <span class=kt>void</span> <span class=nf>Empty</span><span class=p>();</span> 88</span></span><span class=line><span class=cl> <span class=kt>void</span> <span class=nf>Print</span><span class=p>();</span> 89</span></span><span class=line><span class=cl> 90</span></span><span class=line><span class=cl> <span class=k>private</span><span class=o>:</span> 91</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>Insert</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>,</span> <span class=n>T</span> <span class=n>data</span><span class=p>);</span> 92</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>Find</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>,</span> <span class=n>T</span> <span class=n>data</span><span class=p>);</span> 93</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>Remove</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>,</span> <span class=n>T</span> <span class=n>data</span><span class=p>);</span> 94</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>FindPredecessor</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>);</span> 95</span></span><span class=line><span class=cl> <span class=kt>void</span> <span class=nf>Print</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>);</span> 96</span></span><span class=line><span class=cl> <span class=kt>void</span> <span class=nf>Empty</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>);</span> 97</span></span><span class=line><span class=cl><span class=p>};</span> 98</span></span></code></pre></td></tr></table></div></div><p>Â </p><p>Now that we have the forward declarations completed for the methods, it’s time to start defining the constructors and destructor. Since each node will be created using the <code>new</code> keyword, we’ll need to make sure to have a destructor that can <code>delete</code> each of them when we’re done with the BST to avoid a memory leak. We can easily do this by calling the <code>Empty</code> method that we’ll define later on.</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 99</span><span class=lnt> 2 100</span><span class=lnt> 3 101</span><span class=lnt> 4 102</span><span class=lnt> 5 103</span><span class=lnt> 6 104</span><span class=lnt> 7 105</span><span class=lnt> 8 106</span><span class=lnt> 9 107</span><span class=lnt>10 108</span><span class=lnt>11 109</span><span class=lnt>12 110</span><span class=lnt>13 111</span><span class=lnt>14 112</span><span class=lnt>15 113</span><span class=lnt>16 114</span><span class=lnt>17 115</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=c1>//Default constructor 116</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 117</span></span><span class=line><span class=cl><span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>BST</span><span class=p>()</span> <span class=p>{</span> 118</span></span><span class=line><span class=cl> <span class=n>root</span> <span class=o>=</span> <span class=k>nullptr</span><span class=p>;</span> 119</span></span><span class=line><span class=cl><span class=p>}</span> 120</span></span><span class=line><span class=cl> 121</span></span><span class=line><span class=cl><span class=c1>//Constructor with initial value for root 122</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 123</span></span><span class=line><span class=cl><span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>BST</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 124</span></span><span class=line><span class=cl> <span class=n>root</span> <span class=o>=</span> <span class=k>new</span> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>></span><span class=p>(</span><span class=n>data</span><span class=p>);</span> 125</span></span><span class=line><span class=cl><span class=p>}</span> 126</span></span><span class=line><span class=cl> 127</span></span><span class=line><span class=cl><span class=c1>//Destructor 128</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 129</span></span><span class=line><span class=cl><span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::~</span><span class=n>BST</span><span class=p>()</span> <span class=p>{</span> 130</span></span><span class=line><span class=cl> <span class=n>Empty</span><span class=p>();</span> 131</span></span><span class=line><span class=cl><span class=p>}</span> 132</span></span></code></pre></td></tr></table></div></div><p>
132Â </p><h4 id=searching>Searching</h4><p>The first method we’ll look at is searching. Using recursion and the properties of Binary Search Trees, we can quickly find values in our tree. The recursive method will have 2 base cases: the current node is a <code>nullptr</code>, meaning the value doesn’t exist in the tree, or the current node contains the value. If the value isfound, we return the pointer to the node containing the value. If the value isn’t found, we’ll return a <code>nullptr</code> to let the program know the value doesn’t exist. This case will need to be handled each time the Find method is called. To recursively find the value, we compare the current data in the current node to the value being searched for. If the data in the current node is less than the value being searched for we recursively call the Find method with the left leaf node, and if its greater than the value being searched for we call the Find method with the right leaf node.</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 133</span><span class=lnt> 2 134</span><span class=lnt> 3 135</span><span class=lnt> 4 136</span><span class=lnt> 5 137</span><span class=lnt> 6 138</span><span class=lnt> 7 139</span><span class=lnt> 8 140</span><span class=lnt> 9 141</span><span class=lnt>10 142</span><span class=lnt>11 143</span><span class=lnt>12 144</span><span class=lnt>13 145</span><span class=lnt>14 146</span><span class=lnt>15 147</span><span class=lnt>16 148</span><span class=lnt>17 149</span><span class=lnt>18 150</span><span class=lnt>19 151</span><span class=lnt>20 152</span><span class=lnt>21 153</span><span class=lnt>22 154</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=c1>//Public Find method. Returns a nullptr if value isn't found. 155</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 156</span></span><span class=line><span class=cl><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Find</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 157</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=nf>Find</span><span class=p>(</span><span class=n>root</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 158</span></span><span class=line><span class=cl><span class=p>}</span> 159</span></span><span class=line><span class=cl> 160</span></span><span class=line><span class=cl><span class=c1>//Private helper method 161</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 162</span></span><span class=line><span class=cl><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Find</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>,</span> <span class=n>T</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 163</span></span><span class=line><span class=cl> <span class=k>if</span> <span class=p>(</span><span class=n>root</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 164</span></span><span class=line><span class=cl> <span class=c1>//Value was not found in the tree 165</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=k>return</span> <span class=k>nullptr</span><span class=p>;</span> 166</span></span><span class=line><span class=cl> <span class=p>}</span> 167</span></span><span class=line><span class=cl> 168</span></span><span class=line><span class=cl> <span class=k>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o>==</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 169</span></span><span class=line><span class=cl>
169 <span class=k>return</span> <span class=n>root</span><span class=p>;</span> 170</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=nf>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o>></span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 171</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>Find</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 172</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 173</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=nf>Find</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 174</span></span><span class=line><span class=cl> <span class=p>}</span> 175</span></span><span class=line><span class=cl><span class=p>}</span> 176</span></span></code></pre></td></tr></table></div></div><p>Â </p><h4 id=insertion>Insertion</h4><p>Inserting data into a Binary Search Tree is only slightly more complicated than searching for a value. In this example, the Insert method will return a pointer to the inserted node, but if this isn’t needed the methods can return void or a boolean indicating a successful insertion. The base case for our recursion will either be when the current node is a <code>nullptr</code>, meaning that the node is empty, or when the data in the current node is equal to the data to be inserted. In the first case, we’ll instantiate a new node containing our data and return it. In the second case, we’ll return the node that already exists with our value. To get to our base cases, we will take advantage of the BST properties in the same way as we did when searching.</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 177</span><span class=lnt> 2 178</span><span class=lnt> 3 179</span><span class=lnt> 4 180</span><span class=lnt> 5 181</span><span class=lnt> 6 182</span><span class=lnt> 7 183</span><span class=lnt> 8 184</span><span class=lnt> 9 185</span><span class=lnt>10 186</span><span class=lnt>11 187</span><span class=lnt>12 188</span><span class=lnt>13 189</span><span class=lnt>14 190</span><span class=lnt>15 191</span><span class=lnt>16 192</span><span class=lnt>17 193</span><span class=lnt>18 194</span><span class=lnt>19 195</span><span class=lnt>20 196</span><span class=lnt>21 197</span><span class=lnt>22 198</span><span class=lnt>23 199</span><span class=lnt>24 200</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=c1>//Public Insert method 201</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 202</span></span><span class=line><span class=cl><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Insert</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 203</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=nf>Insert</span><span class=p>(</span><span class=n>root</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 204</span></span><span class=line><span class=cl><span class=p>}</span> 205</span></span><span class=line><span class=cl> 206</span></span><span class=line><span class=cl><span class=c1>//Private helper method 207</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 208</span></span><span class=line><span class=cl><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Insert</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>,</span> <span class=n>T</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 209</span></span><span class=line><span class=cl> <span class=k>if</span> <span class=p>(</span><span class=n>root</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 210</span></span><span class=line><span class=cl>
210 <span class=n>root</span> <span class=o>=</span> <span class=k>new</span> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>></span><span class=p>(</span><span class=n>data</span><span class=p>);</span> 211</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>root</span><span class=p>;</span> 212</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=nf>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o>==</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 213</span></span><span class=line><span class=cl> <span class=c1>//Already exists, return the existing object 214</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=k>return</span> <span class=n>root</span><span class=p>;</span> 215</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=nf>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o>></span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 216</span></span><span class=line><span class=cl> <span class=c1>//Root data is greater than data to be inserted, so recursively insert on the left leaf 217</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=n>root</span><span class=o>-></span><span class=n>left</span> <span class=o>=</span> <span class=n>Insert</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 218</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span><span class=p>{</span> 219</span></span><span class=line><span class=cl> <span class=c1>//Root data is less than data to be inserted, so recursively insert on the right leaf 220</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=n>root</span><span class=o>-></span><span class=n>right</span> <span class=o>=</span> <span class=n>Insert</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 221</span></span><span class=line><span class=cl> <span class=p>}</span> 222</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>root</span><span class=p>;</span> 223</span></span><span class=line><span class=cl><span class=p>}</span> 224</span></span></code></pre></td></tr></table></div></div><p>Â </p><h4 id=removal>Removal</h4><p>Removing a node is perhaps the most complicated algorithm for a Binary Search Tree. When removing a node, there are three main cases:</p><ol><li>The node to be removed has no children (easiest)</li><li>The node to be removed has one child</li><li>The node to be removed has two children (most complicated)</li></ol><p>Below is the full code for removing a value from the BST. Included is a FindPredecessor method that will be used in the third case (this will be discussed in more detail shortly).</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 225</span><span class=lnt> 2 226</span><span class=lnt> 3 227</span><span class=lnt> 4 228</span><span class=lnt> 5 229</span><span class=lnt> 6 230</span><span class=lnt> 7 231</span><span class=lnt> 8 232</span><span class=lnt> 9 233</span><span class=lnt>10 234</span><span class=lnt>11 235</span><span class=lnt>12 236</span><span class=lnt>13 237</span><span class=lnt>14 238</span><span class=lnt>15 239</span><span class=lnt>16 240</span><span class=lnt>17 241</span><span class=lnt>18 242</span><span class=lnt>19 243</span><span class=lnt>20 244</span><span class=lnt>21 245</span><span class=lnt>22 246</span><span class=lnt>23 247</span><span class=lnt>24 248</span><span class=lnt>25 249</span><span class=lnt>26 250</span><span class=lnt>27 251</span><span class=lnt>28 252</span><span class=lnt>29 253</span><span class=lnt>30 254</span><span class=lnt>31 255</span><span class=lnt>32 256</span><span class=lnt>33 257</span><span class=lnt>34 258</span><span class=lnt>35 259</span><span class=lnt>36 260</span><span class=lnt>37 261</span><span class=lnt>38 262</span><span class=lnt>39 263</span><span class=lnt>40 264</span><span class=lnt>41 265</span><span class=lnt>42 266</span><span class=lnt>43 267</span><span class=lnt>44 268</span><span class=lnt>45 269</span><span class=lnt>46 270</span><span class=lnt>47 271</span><span class=lnt>48 272</span><span class=lnt>49 273</span><span class=lnt>50 274</span><span class=lnt>51 275</span><span class=lnt>52 276</span><span class=lnt>53 277</span><span class=lnt>54 278</span><span class=lnt>55 279</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=c1>//Public Remove method 280</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 281</span></span><span class=line><span class=cl><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Remove</span><span class=p>(</span><span class=n>T</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 282</span></span><span class=line><span class=cl> <span class=n>root</span> <span class=o>=</span> <span class=n>Remove</span><span class=p>(</span><span class=n>root</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 283</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>root</span><span class=p>;</span> 284</span></span><span class=line><span class=cl><span class=p>}</span> 285</span></span><span class=line><span class=cl> 286</span></span><span class=line><span class=cl><span class=c1>//Private helper method 287</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 288</span></span><span class=line><span class=cl><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Remove</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>,</span> <span class=n>T</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 289</span></span><span class=line><span class=cl> <span class=k>if</span> <span class=p>(</span><span class=n>root</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 290</span></span><span class=line><span class=cl>
290 <span class=k>return</span> <span class=k>nullptr</span><span class=p>;</span> 291</span></span><span class=line><span class=cl> <span class=p>}</span> 292</span></span><span class=line><span class=cl> 293</span></span><span class=line><span class=cl> <span class=c1>//Recusively look for the node to be deleted 294</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=k>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o>></span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 295</span></span><span class=line><span class=cl> <span class=n>root</span><span class=o>-></span><span class=n>left</span> <span class=o>=</span> <span class=n>Remove</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 296</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=nf>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o><</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 297</span></span><span class=line><span class=cl> <span class=n>root</span><span class=o>-></span><span class=n>right</span> <span class=o>=</span> <span class=n>Remove</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 298</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 299</span></span><span class=line><span class=cl> <span class=c1>//Node was found 300</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=c1>//3 cases to handle now: node is a leaf, node has one child, and node has 2 children 301</span></span></span><span class=line><span class=cl><span class=c1></span> 302</span></span><span class=line><span class=cl> <span class=c1>//Node is a leaf: 303</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=k>if</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span> <span class=o>==</span> <span class=k>nullptr</span> <span class=o>&&</span> <span class=n>root</span><span class=o>-></span><span class=n>right</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 304</span></span><span class=line><span class=cl> <span class=k>delete</span> <span class=n>root</span><span class=p>;</span> 305</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=k>nullptr</span><span class=p>;</span> 306</span></span><span class=line><span class=cl> <span class=c1>//Node has one child: 307</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=p>}</span> <span class=k>else</span> <span class=nf>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 308</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>temp</span> <span class=o>=</span> <span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>;</span> 309</span></span><span class=line><span class=cl> <span class=k>delete</span> <span class=n>root</span><span class=p>;</span> 310</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>temp</span><span class=p>;</span> 311</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=nf>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 312</span></span><span class=line><span class=cl>
312 <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>temp</span> <span class=o>=</span> <span class=n>root</span><span class=o>-></span><span class=n>right</span><span class=p>;</span> 313</span></span><span class=line><span class=cl> <span class=k>delete</span> <span class=n>root</span><span class=p>;</span> 314</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>temp</span><span class=p>;</span> 315</span></span><span class=line><span class=cl> <span class=c1>//Node has two children: 316</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 317</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>pred</span> <span class=o>=</span> <span class=n>FindPredecessor</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>);</span> 318</span></span><span class=line><span class=cl> <span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o>=</span> <span class=n>pred</span><span class=o>-></span><span class=n>data</span><span class=p>;</span> 319</span></span><span class=line><span class=cl> <span class=n>root</span><span class=o>-></span><span class=n>left</span> <span class=o>=</span> <span class=n>Remove</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>,</span> <span class=n>pred</span><span class=o>-></span><span class=n>data</span><span class=p>);</span> 320</span></span><span class=line><span class=cl> <span class=p>}</span> 321</span></span><span class=line><span class=cl> <span class=p>}</span> 322</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>root</span><span class=p>;</span> 323</span></span><span class=line><span class=cl><span class=p>}</span> 324</span></span><span class=line><span class=cl> 325</span></span><span class=line><span class=cl><span class=c1>//Find the right most node in the left subtree 326</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 327</span></span><span class=line><span class=cl><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>FindPredecessor</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>)</span> <span class=p>{</span> 328</span></span><span class=line><span class=cl> <span class=k>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 329</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>root</span><span class=p>;</span> 330</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 331</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=nf>FindPredecessor</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span><span class=p>);</span> 332</span></span><span class=line><span class=cl> <span class=p>}</span> 333</span></span><span class=line><span class=cl><span class=p>}</span> 334</span></span></code></pre></td></tr></table></div></div><p>Â </p><p>Now that we’ve seen the complete code, let’s break it down into smaller pieces. The first part of the method looks very similar to the Find method we wrote earlier, with one change. When a node is deleted, we need to update the parent nodes pointer so that it doesn’t point to a deleted object. By assigning root->left or root->right to the corresponding recursive Remove call, we can make sure all the pointers are going to the correct objects and keep our tree intact.</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 335</span><span class=lnt> 2 336</span><span class=lnt> 3 337</span><span class=lnt> 4 338</span><span class=lnt> 5 339</span><span class=lnt> 6 340</span><span class=lnt> 7 341</span><span class=lnt> 8 342</span><span class=lnt> 9 343</span><span class=lnt>10 344</span><span class=lnt>11 345</span><span class=lnt>12 346</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=k>if</span> <span class=p>(</span><span class=n>root</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 347</span></span><span class=line><span class=cl> <span class=c1>//Node wasn't found, return a nullptr 348</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=k>return</span> <span class=k>nullptr</span><span class=p>;</span> 349</span></span><span class=line><span class=cl><span class=p>}</span> 350</span></span><span class=line><span class=cl> 351</span></span><span class=line><span class=cl><span class=c1>//Recusively look for the node to be deleted 352</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o>></span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 353</span></span><span class=line><span class=cl> <span class=n>root</span><span class=o>-></span><span class=n>left</span> <span class=o>=</span> <span class=n>Remove</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 354</span></span><span class=line><span class=cl><span class=p>}</span> <span class=k>else</span> <span class=nf>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o><</span> <span class=n>data</span><span class=p>)</span> <span class=p>{</span> 355</span></span><span class=line><span class=cl> <span class=n>root</span><span class=o>-></span><span class=n>right</span> <span class=o>=</span> <span class=n>Remove</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span><span class=p>,</span> <span class=n>data</span><span class=p>);</span> 356</span></span><span class=line><span class=cl><span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 357</span></span><span class=line><span class=cl> <span class=c1>// node is found, do stuff ... 358</span></span></span></code></pre></td></tr></table></div></div><p>
358Â </p><h6 id=case-1-node-has-no-children>Case 1: Node Has No Children</h6><p>Now that we’ve found the node we want to delete, we must determine which of the three cases this node falls under. If the node has no children, we just need to remove the node and return a <code>nullptr</code> to the parent. This is the easiest of the three cases. The two images below show an example tree before and after a leaf node is removed.</p><p><img class=lazyload src=/svg/loading.min.svg data-src=/images/BSTRemove11.png data-srcset="/images/BSTRemove11.png, /images/BSTRemove11.png 1.5x, /images/BSTRemove11.png 2x" data-sizes=auto alt=/images/BSTRemove11.png title="Tree before leaf node removal"> 359<img class=lazyload src=/svg/loading.min.svg data-src=/images/BSTRemove12.png data-srcset="/images/BSTRemove12.png, /images/BSTRemove12.png 1.5x, /images/BSTRemove12.png 2x" data-sizes=auto alt=/images/BSTRemove12.png title="Tree after leaf node removal"></p><p>Â </p><p>Below is the code removing a leaf node:</p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt>1 360</span><span class=lnt>2 361</span><span class=lnt>3 362</span><span class=lnt>4 363</span><span class=lnt>5 364</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=c1>//Node is a leaf: 365</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span> <span class=o>==</span> <span class=k>nullptr</span> <span class=o>&&</span> <span class=n>root</span><span class=o>-></span><span class=n>right</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 366</span></span><span class=line><span class=cl> <span class=k>delete</span> <span class=n>root</span><span class=p>;</span> 367</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=k>nullptr</span><span class=p>;</span> 368</span></span><span class=line><span class=cl><span class=p>}</span> 369</span></span></code></pre></td></tr></table></div></div><p>Â </p><h6 id=case-2-node-has-one-child>Case 2: Node Has One Child</h6><p>For the second case, removal gets slightly more complicated. We must now replace the node we delete with its child node. To accomplish this, we can store the pointer to the child in a temporary variable, delete the current node, and return the pointer to the child back to the original parent node. The two images below show an example tree before and after the node is removed.</p><p><img class=lazyload src=/svg/loading.min.svg data-src=/images/BSTRemove21.png data-srcset="/images/BSTRemove21.png, /images/BSTRemove21.png 1.5x, /images/BSTRemove21.png 2x" data-sizes=auto alt=/images/BSTRemove21.png title="Tree before node removal"> 370<img class=lazyload src=/svg/loading.min.svg data-src=/images/BSTRemove22.png data-srcset="/images/BSTRemove22.png, /images/BSTRemove22.png 1.5x, /images/BSTRemove22.png 2x" data-sizes=auto alt=/images/BSTRemove22.png title="Tree after node removal"></p><p>Â </p><p>Below is the code for this case:</p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 371</span><span class=lnt> 2 372</span><span class=lnt> 3 373</span><span class=lnt> 4 374</span><span class=lnt> 5 375</span><span class=lnt> 6 376</span><span class=lnt> 7 377</span><span class=lnt> 8 378</span><span class=lnt> 9 379</span><span class=lnt>10 380</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=c1>//Node has one child: 381</span></span></span><span class=line><span class=cl><span class=c1></span><span class=p>}</span> <span class=k>else</span> <span class=nf>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 382</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>temp</span> <span class=o>=</span> <span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>;</span> 383</span></span><span class=line><span class=cl> <span class=k>delete</span> <span class=n>root</span><span class=p>;</span> 384</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>temp</span><span class=p>;</span> 385</span></span><span class=line><span class=cl><span class=p>}</span> <span class=k>else</span> <span class=nf>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 386</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>temp</span> <span class=o>=</span> <span class=n>root</span><span class=o>-></span><span class=n>right</span><span class=p>;</span> 387</span></span><span class=line><span class=cl> <span class=k>delete</span> <span class=n>root</span><span class=p>;</span> 388</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>temp</span><span class=p>;</span> 389</span></span><span class=line><span class=cl><span class=p>}</span> 390</span></span></code></pre></td></tr></table></div></div><p>
390Â </p><h6 id=case-3-node-has-two-children>Case 3: Node Has Two Children</h6><p>The final case is the most complicated of the three. When the node has two children, we must find the proper value to replace it with. The first thing that may come to mind is to use one of the children, however in many cases this will violate the properties of a BST by having values in improper locations. What we need to do is replace the value with either the next smallest value or the next largest. Considering the properties of a BST, we know that the next smallest value will be in the left subtree and as far right in that subtree as we can go. This node is called the <em>predecessor</em>. The next largest value is in the right subtree of the node we want to remove and as far left in that subtree as we can go. This is called the <em>ancestor</em>. Either value is perfectly fine to use, but in this example I used the predecessor.</p><p>The two images below show an example of what a tree will look like before and after removing a node with two children:</p><p><img class=lazyload src=/svg/loading.min.svg data-src=/images/BSTRemove31.png data-srcset="/images/BSTRemove31.png, /images/BSTRemove31.png 1.5x, /images/BSTRemove31.png 2x" data-sizes=auto alt=/images/BSTRemove31.png title="Tree before node removal"> 391<img class=lazyload src=/svg/loading.min.svg data-src=/images/BSTRemove32.png data-srcset="/images/BSTRemove32.png, /images/BSTRemove32.png 1.5x, /images/BSTRemove32.png 2x" data-sizes=auto alt=/images/BSTRemove32.png title="Tree after node removal"></p><p>Â </p><p>Let’s take a look at the FindPredecessor method. When we initially call this method, we’ll call it on <code>root->left</code> to get started searching the left subtree. Then, the method will recursively go to the right until reaching the base case when the current node does not have a right leaf. We’ve reached the predecessor and will return a pointer to this node.</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt>1 392</span><span class=lnt>2 393</span><span class=lnt>3 394</span><span class=lnt>4 395</span><span class=lnt>5 396</span><span class=lnt>6 397</span><span class=lnt>7 398</span><span class=lnt>8 399</span><span class=lnt>9 400</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=c1>//Find the right most node in the left subtree 401</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 402</span></span><span class=line><span class=cl><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>FindPredecessor</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>)</span> <span class=p>{</span> 403</span></span><span class=line><span class=cl> <span class=k>if</span> <span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 404</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=n>root</span><span class=p>;</span> 405</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 406</span></span><span class=line><span class=cl> <span class=k>return</span> <span class=nf>FindPredecessor</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span><span class=p>);</span> 407</span></span><span class=line><span class=cl> <span class=p>}</span> 408</span></span><span class=line><span class=cl><span class=p>}</span> 409</span></span></code></pre></td></tr></table></div></div><p>
409Â </p><p>Now that we can find the predecessor, we can finish the last part of the Remove method. Below is the code for replacing the node to be deleted with the predecessor. Note that we don’t actually <code>delete</code> anything there like we did in the first two cases. Instead, we replace the <code>data</code> variable of the existing node with the predecessor’s <code>data</code>. Since we now have two nodes with the same value, we call the remove method on the left subtree and remove the predecessor.</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt>1 410</span><span class=lnt>2 411</span><span class=lnt>3 412</span><span class=lnt>4 413</span><span class=lnt>5 414</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 415</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>pred</span> <span class=o>=</span> <span class=n>FindPredecessor</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>);</span> 416</span></span><span class=line><span class=cl> <span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o>=</span> <span class=n>pred</span><span class=o>-></span><span class=n>data</span><span class=p>;</span> 417</span></span><span class=line><span class=cl> <span class=n>root</span><span class=o>-></span><span class=n>left</span> <span class=o>=</span> <span class=n>Remove</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>,</span> <span class=n>pred</span><span class=o>-></span><span class=n>data</span><span class=p>);</span> 418</span></span><span class=line><span class=cl><span class=p>}</span> 419</span></span></code></pre></td></tr></table></div></div><p>Â </p><h4 id=emptying-the-tree>Emptying The Tree</h4><p>Now it’s time to finish the Empty method that was put in the destructor. To empty the tree, we need to recursively delete every item in the tree from heap memory due to the lack of garbage collection in C++. This is much easier than removing an individual node because we can start at the leaf nodes and work back up the tree using a postorder traversal. Postorder traversals visit the left node, the right node, then the root node. Finally, we’ll set the root variable to <code>nullptr</code>.</p><p>Basic postorder traversal:</p><ol><li>Recursive call on left subtree</li><li>Recursive call on right subtree</li><li>Visit node (in this case, delete the node)</li></ol><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 420</span><span class=lnt> 2 421</span><span class=lnt> 3 422</span><span class=lnt> 4 423</span><span class=lnt> 5 424</span><span class=lnt> 6 425</span><span class=lnt> 7 426</span><span class=lnt> 8 427</span><span class=lnt> 9 428</span><span class=lnt>10 429</span><span class=lnt>11 430</span><span class=lnt>12 431</span><span class=lnt>13 432</span><span class=lnt>14 433</span><span class=lnt>15 434</span><span class=lnt>16 435</span><span class=lnt>17 436</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 437</span></span><span class=line><span class=cl><span class=kt>void</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Empty</span><span class=p>()</span> <span class=p>{</span> 438</span></span><span class=line><span class=cl> <span class=n>Empty</span><span class=p>(</span><span class=n>root</span><span class=p>);</span> 439</span></span><span class=line><span class=cl> <span class=n>root</span> <span class=o>=</span> <span class=k>nullptr</span><span class=p>;</span> 440</span></span><span class=line><span class=cl><span class=p>}</span> 441</span></span><span class=line><span class=cl> 442</span></span><span class=line><span class=cl><span class=c1>//Using postorder traveral to delete all objects on the heap 443</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 444</span></span><span class=line><span class=cl><span class=kt>void</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Empty</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>)</span> <span class=p>{</span> 445</span></span><span class=line><span class=cl> <span class=k>if</span> <span class=p>(</span><span class=n>root</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 446</span></span><span class=line><span class=cl>
446 <span class=k>return</span><span class=p>;</span> 447</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 448</span></span><span class=line><span class=cl> <span class=n>Empty</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>);</span> 449</span></span><span class=line><span class=cl> <span class=n>Empty</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span><span class=p>);</span> 450</span></span><span class=line><span class=cl> <span class=k>delete</span> <span class=n>root</span><span class=p>;</span> 451</span></span><span class=line><span class=cl> <span class=p>}</span> 452</span></span><span class=line><span class=cl><span class=p>}</span> 453</span></span></code></pre></td></tr></table></div></div><p>Â </p><h4 id=printing-the-nodes>Printing The Nodes</h4><p>The final method for our templated tree is a Print method. In this implementation, I used an inorder traversal to print the nodes. As opposed to the postorder traversal, an inorder traversal goes left child, root node, right child. This will print the values in the tree from least to greatest. The difference between postorder and inorder only involves flipping two lines of code. For the inorder traversal, the ‘visit’ happens before the recursive call on the right subtree:</p><p>Basic inorder traversal:</p><ol><li>Recursive call on left subtree</li><li>Visit node (in this case, print the node to console)</li><li>Recursive call on right subtree</li></ol><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 454</span><span class=lnt> 2 455</span><span class=lnt> 3 456</span><span class=lnt> 4 457</span><span class=lnt> 5 458</span><span class=lnt> 6 459</span><span class=lnt> 7 460</span><span class=lnt> 8 461</span><span class=lnt> 9 462</span><span class=lnt>10 463</span><span class=lnt>11 464</span><span class=lnt>12 465</span><span class=lnt>13 466</span><span class=lnt>14 467</span><span class=lnt>15 468</span><span class=lnt>16 469</span><span class=lnt>17 470</span><span class=lnt>18 471</span><span class=lnt>19 472</span><span class=lnt>20 473</span><span class=lnt>21 474</span><span class=lnt>22 475</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=c1>//Public print method 476</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 477</span></span><span class=line><span class=cl><span class=kt>void</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Print</span><span class=p>()</span> <span class=p>{</span> 478</span></span><span class=line><span class=cl> <span class=k>if</span> <span class=p>(</span><span class=n>root</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 479</span></span><span class=line><span class=cl> <span class=n>std</span><span class=o>::</span><span class=n>cout</span> <span class=o><<</span> <span class=s>"Empty Tree"</span> <span class=o><<</span> <span class=n>std</span><span class=o>::</span><span class=n>endl</span><span class=p>;</span> 480</span></span><span class=line><span class=cl> <span class=k>return</span><span class=p>;</span> 481</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 482</span></span><span class=line><span class=cl> <span class=n>Print</span><span class=p>(</span><span class=n>root</span><span class=p>);</span> 483</span></span><span class=line><span class=cl> <span class=p>}</span> 484</span></span><span class=line><span class=cl><span class=p>}</span> 485</span></span><span class=line><span class=cl> 486</span></span><span class=line><span class=cl><span class=c1>//Private helper method 487</span></span></span><span class=line><span class=cl><span class=c1></span><span class=k>template</span> <span class=o><</span><span class=k>typename</span> <span class=n>T</span><span class=o>></span> 488</span></span><span class=line><span class=cl><span class=kt>void</span> <span class=n>BST</span><span class=o><</span><span class=n>T</span><span class=o>>::</span><span class=n>Print</span><span class=p>(</span><span class=n>Node</span><span class=o><</span><span class=n>T</span><span class=o>>*</span> <span class=n>root</span><span class=p>)</span> <span class=p>{</span> 489</span></span><span class=line><span class=cl> <span class=k>if</span> <span class=p>(</span><span class=n>root</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 490</span></span><span class=line><span class=cl>
490 <span class=k>return</span><span class=p>;</span> 491</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 492</span></span><span class=line><span class=cl> <span class=n>Print</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>left</span><span class=p>);</span> 493</span></span><span class=line><span class=cl> <span class=n>std</span><span class=o>::</span><span class=n>cout</span> <span class=o><<</span> <span class=n>root</span><span class=o>-></span><span class=n>data</span> <span class=o><<</span> <span class=s>" "</span><span class=p>;</span> 494</span></span><span class=line><span class=cl> <span class=n>Print</span><span class=p>(</span><span class=n>root</span><span class=o>-></span><span class=n>right</span><span class=p>);</span> 495</span></span><span class=line><span class=cl> <span class=p>}</span> 496</span></span><span class=line><span class=cl><span class=p>}</span> 497</span></span></code></pre></td></tr></table></div></div><p>Â </p><h4 id=conclusion>Conclusion</h4><p>This complete templated Binary Search Tree can be used with any data type in C++ that can be compared with comparison operators (==, >, <, etc). To use the templated BST with custom class objects, the comparison operators will need to be overloaded in that class to allow objects to be compared with each other. Operator overloading isn’t covered in this post, but there are many good resources online covering this topic.</p><p>Below is some example code showing the versatility of a templated class.</p><p>Â </p><div class=highlight><div class=chroma><table class=lntable><tr><td class=lntd><pre tabindex=0 class=chroma><code><span class=lnt> 1 498</span><span class=lnt> 2 499</span><span class=lnt> 3 500</span><span class=lnt> 4 501</span><span class=lnt> 5 502</span><span class=lnt> 6 503</span><span class=lnt> 7 504</span><span class=lnt> 8 505</span><span class=lnt> 9 506</span><span class=lnt>10 507</span><span class=lnt>11 508</span><span class=lnt>12 509</span><span class=lnt>13 510</span><span class=lnt>14 511</span><span class=lnt>15 512</span><span class=lnt>16 513</span><span class=lnt>17 514</span><span class=lnt>18 515</span><span class=lnt>19 516</span><span class=lnt>20 517</span><span class=lnt>21 518</span><span class=lnt>22 519</span><span class=lnt>23 520</span><span class=lnt>24 521</span><span class=lnt>25 522</span><span class=lnt>26 523</span><span class=lnt>27 524</span><span class=lnt>28 525</span><span class=lnt>29 526</span><span class=lnt>30 527</span><span class=lnt>31 528</span><span class=lnt>32 529</span><span class=lnt>33 530</span><span class=lnt>34 531</span><span class=lnt>35 532</span><span class=lnt>36 533</span><span class=lnt>37 534</span><span class=lnt>38 535</span><span class=lnt>39 536</span><span class=lnt>40 537</span><span class=lnt>41 538</span><span class=lnt>42 539</span><span class=lnt>43 540</span><span class=lnt>44 541</span><span class=lnt>45 542</span><span class=lnt>46 543</span><span class=lnt>47 544</span><span class=lnt>48 545</span><span class=lnt>49 546</span><span class=lnt>50 547</span><span class=lnt>51 548</span></code></pre></td><td class=lntd><pre tabindex=0 class=chroma><code class=language-cpp data-lang=cpp><span class=line><span class=cl><span class=kt>int</span> <span class=nf>main</span> <span class=p>(</span><span class=kt>int</span> <span class=n>argc</span><span class=p>,</span> <span class=kt>char</span><span class=o>**</span> <span class=n>argv</span><span class=p>)</span> <span class=p>{</span> 549</span></span><span class=line><span class=cl> 550</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=n>endl</span> <span class=o><<</span> <span class=n>endl</span><span class=p>;</span> 551</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=s>"Integer Tree:"</span><span class=p>;</span> 552</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=n>endl</span> <span class=o><<</span> <span class=n>
552endl</span><span class=p>;</span> 553</span></span><span class=line><span class=cl> <span class=c1>//Create an integer BST with an inital root of 25 554</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=n>BST</span><span class=o><</span><span class=kt>int</span><span class=o>>*</span> <span class=n>tree</span> <span class=o>=</span> <span class=k>new</span> <span class=n>BST</span><span class=o><</span><span class=kt>int</span><span class=o>></span><span class=p>(</span><span class=mi>25</span><span class=p>);</span> 555</span></span><span class=line><span class=cl> <span class=n>tree</span><span class=o>-></span><span class=n>Insert</span><span class=p>(</span><span class=mi>20</span><span class=p>);</span> 556</span></span><span class=line><span class=cl> <span class=n>tree</span><span class=o>-></span><span class=n>Insert</span><span class=p>(</span><span class=mi>12</span><span class=p>);</span> 557</span></span><span class=line><span class=cl> <span class=n>tree</span><span class=o>-></span><span class=n>Insert</span><span class=p>(</span><span class=o>-</span><span class=mi>10</span><span class=p>);</span> 558</span></span><span class=line><span class=cl> <span class=n>tree</span><span class=o>-></span><span class=n>Insert</span><span class=p>(</span><span class=mi>50</span><span class=p>);</span> 559</span></span><span class=line><span class=cl> 560</span></span><span class=line><span class=cl> <span class=n>tree</span><span class=o>-></span><span class=n>Print</span><span class=p>();</span> 561</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=n>endl</span> <span class=o><<</span> <span class=n>endl</span><span class=p>;</span> 562</span></span><span class=line><span class=cl> 563</span></span><span class=line><span class=cl> <span class=n>tree</span><span class=o>-></span><span class=n>Remove</span><span class=p>(</span><span class=mi>12</span><span class=p>);</span> 564</span></span><span class=line><span class=cl> <span class=n>tree</span><span class=o>-></span><span class=n>Print</span><span class=p>();</span> 565</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=n>endl</span> <span class=o><<</span> <span class=n>endl</span><span class=p>;</span> 566</span></span><span class=line><span class=cl> 567</span></span><span class=line><span class=cl> <span class=n>Node</span><span class=o><</span><span class=kt>int</span><span class=o>>*</span> <span class=n>node</span> <span class=o>=</span> <span class=n>tree</span><span class=o>-></span><span class=n>Find</span><span class=p>(</span><span class=mi>2</span><span class=p>);</span> 568</span></span><span class=line><span class=cl> <span class=k>if</span> <span class=p>(</span><span class=n>node</span> <span class=o>==</span> <span class=k>nullptr</span><span class=p>)</span> <span class=p>{</span> 569</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=s>"not found"</span> <span class=o><<</span> <span class=n>endl</span><span class=p>;</span> 570</span></span><span class=line><span class=cl> <span class=p>}</span> <span class=k>else</span> <span class=p>{</span> 571</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=n>node</span><span class=o>-></span><span class=n>data</span> <span class=o><<</span> <span class=n>endl</span><span class=p>;</span> 572</span></span><span class=line><span class=cl> <span class=p>}</span> 573</span></span><span class=line><span class=cl> <span class=k>delete</span><span class=p>(</span><span class=n>tree</span><span class=p>);</span> 574</span></span><span class=line><span class=cl> 575</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=n>endl</span> <span class=o><<</span> <span class=n>
575endl</span> <span class=o><<</span> <span class=n>endl</span> <span class=o><<</span> <span class=n>endl</span><span class=p>;</span> 576</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=s>"Character Tree:"</span><span class=p>;</span> 577</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=n>endl</span> <span class=o><<</span> <span class=n>endl</span><span class=p>;</span> 578</span></span><span class=line><span class=cl> 579</span></span><span class=line><span class=cl> <span class=c1>//Create a character BST 580</span></span></span><span class=line><span class=cl><span class=c1></span> <span class=n>BST</span><span class=o><</span><span class=kt>char</span><span class=o>>*</span> <span class=n>cTree</span> <span class=o>=</span> <span class=k>new</span> <span class=n>BST</span><span class=o><</span><span class=kt>char</span><span class=o>></span><span class=p>(</span><span class=sc>'k'</span><span class=p>);</span> 581</span></span><span class=line><span class=cl> <span class=n>cTree</span><span class=o>-></span><span class=n>Print</span><span class=p>();</span> 582</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=n>endl</span> <span class=o><<</span> <span class=n>endl</span><span class=p>;</span> 583</span></span><span class=line><span class=cl> 584</span></span><span class=line><span class=cl> <span class=n>cTree</span><span class=o>-></span><span class=n>Insert</span><span class=p>(</span><span class=sc>'a'</span><span class=p>);</span> 585</span></span><span class=line><span class=cl> <span class=n>cTree</span><span class=o>-></span><span class=n>Insert</span><span class=p>(</span><span class=sc>'z'</span><span class=p>);</span> 586</span></span><span class=line><span class=cl> <span class=n>cTree</span><span class=o>-></span><span class=n>Insert</span><span class=p>(</span><span class=sc>'d'</span><span class=p>);</span> 587</span></span><span class=line><span class=cl> <span class=n>cTree</span><span class=o>-></span><span class=n>Insert</span><span class=p>(</span><span class=sc>'s'</span><span class=p>);</span> 588</span></span><span class=line><span class=cl> 589</span></span><span class=line><span class=cl> <span class=n>cTree</span><span class=o>-></span><span class=n>Print</span><span class=p>();</span> 590</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=n>endl</span> <span class=o><<</span> <span class=n>endl</span><span class=p>;</span> 591</span></span><span class=line><span class=cl> 592</span></span><span class=line><span class=cl> <span class=n>cTree</span><span class=o>-></span><span class=n>Remove</span><span class=p>(</span><span class=sc>'k'</span><span class=p>);</span> 593</span></span><span class=line><span class=cl> 594</span></span><span class=line><span class=cl> <span class=n>cTree</span><span class=o>-></span><span class=n>Print</span><span class=p>();</span> 595</span></span><span class=line><span class=cl> <span class=n>cout</span> <span class=o><<</span> <span class=n>endl</span> <span class=o><<</span> <span class=n>endl</span><span class=p>;</span> 596</span></span><span class=line><span class=cl> 597</span></span><span class=line><span class=cl> <span class=k>delete</span><span class=p>(</span><span class=n>cTree</span><span class=p>);</span> 598</span></span><span class=line><span class=cl><span class=p>}</span> 599</span></span></code></pre></td></tr></table></div></div><p> </p><p>Thanks for reading!</p></div><div class=post-footer id=post-footer><div class=post-info><div class=post-info-line><div class=post-info-mod><span>Updated on 2022-08-10</span></div></div><div class=post-info-line><div class=post-info-md></div><div class=post-info-share><span><a href=javascript:void(0); title="Share on Twitter" data-sharer=twitter data-url=https://austinchristiansen.com/posts/bst/ data-title="Binary Search Trees"><i class="fab fa-twitter fa-fw" aria-hidden=true></i></a><a href=javascript:void(0); title="Share on Facebook" data-sharer=facebook data-url=https://austinchristiansen.com/posts/bst/><i class="fab fa-facebook-square fa-fw" aria-hidden=true></i></a><a href=javascript:void(0); title="Share on Linkedin" data-sharer=linkedin data-url=https://austinchristiansen.com/posts/bst/><i class="fab fa-linkedin fa-fw" aria-hidden=true></i></a><a href=javascript:void(0); title="Share on Hacker News" data-sharer=hackernews data-url=https://austinchristiansen.com/posts/bst/ data-title="Binary Search Trees"><i class="fab fa-hacker-news fa-fw" aria-hidden=true></i></a><a href=javascript:void(0); title="Share on Reddit" data-sharer=reddit data-url=https://austinchristiansen.com/posts/bst/><i class="fab fa-reddit fa-fw" aria-hidden=true></i></a><a href=javascript:void(0); title="Share on Line" data-sharer=line data-url=https://austinchristiansen.com/posts/bst/ data-title="Binary Search Trees"><i data-svg-src=https://cdn.jsdelivr.net/npm/[email protected]/icons/line.svg aria-hidden=true></i></a><a href=javascript:void(0); title="Share on å¾®å" data-sharer=weibo data-url=https://austinchristiansen.com/posts/bst/ data-title="Binary Search Trees"><i class="fab fa-weibo fa-fw" aria-hidden=true></i></a></span></div></div></div><div class=post-info-more><section class=post-tags></section><section><span><a href=javascript:void(0); onclick=window.history.back()>Back</a></span> | <span><a href=/>Home</a></span></section></div><div class=post-nav><a href=/posts/tw/ class=next rel=next title="Scheduled Tweets With Cloudflare Workers">Scheduled Tweets With Cloudflare Workers<i class="fas fa-angle-right fa-fw" aria-hidden=true></i></a></div></div></article></div></main><footer class=footer><div class=footer-container><div class=footer-line itemscope itemtype=http://schema.org/CreativeWork><i class="far fa-copyright fa-fw" aria-hidden=true></i><span itemprop=copyrightYear>2022 - 2023</span><span class=author itemprop=copyrightHolder> <a href=/ target=_blank>Austin Christiansen</a></span></div></div></footer></div><div id=fixed-buttons><a href=# id=back-to-top class=fixed-button title="Back to Top"><i class="fas fa-arrow-up fa-fw" aria-hidden=true></i> 600</a><a href=# id=view-comments class=fixed-button title="View Comments"><i class="fas fa-comment fa-fw" aria-hidden=true></i></a></div>
600<script type=text/javascript src=https://cdn.jsdelivr.net/npm/[email protected]/dist/autocomplete.min.js></script>
600<script type=text/javascript src=https://cdn.jsdelivr.net/npm/[email protected]/lunr.min.js></script>
600<script type=text/javascript src=https://cdn.jsdelivr.net/npm/[email protected]/lazysizes.min.js></script>
600<script type=text/javascript src=https://cdn.jsdelivr.net/npm/[email protected]/dist/clipboard.min.js></script>
600<script type=text/javascript src=https://cdn.jsdelivr.net/npm/[email protected]/sharer.min.js></script>
600<script type=text/javascript>window.config={code:{copyTitle:"Copy to clipboard",maxShownLines:60},comment:{},search:{highlightTag:"em",lunrIndexURL:"/index.json",maxResultLength:10,noResultsFound:"No results found",snippetLength:30,type:"lunr"}}</script>
600<script type=text/javascript src=/js/theme.min.js></script>
600</body></html>
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.