{"id":2091,"date":"2018-11-19T22:09:04","date_gmt":"2018-11-19T22:09:04","guid":{"rendered":"https:\/\/danielschlegel.org\/wp\/?page_id=2091"},"modified":"2018-11-19T22:09:05","modified_gmt":"2018-11-19T22:09:05","slug":"binary-search-tree","status":"publish","type":"page","link":"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/","title":{"rendered":"Binary Search Tree"},"content":{"rendered":"\n<pre class=\"java\">\npublic class BST<E extends Comparable<E>>{\n\n    @SuppressWarnings(\"ClassCanBeStatic\")\n    private class BSTNode<U extends Comparable<U>>{\n        BSTNode<U> left, right;\n        U value;\n\n        public BSTNode(U value){\n            this.value = value;\n        }\n\n        \/\/ Adapted from Todd Davies answer to printing a BST on Stack Overflow.\n        \/\/ https:\/\/stackoverflow.com\/questions\/4965335\/how-to-print-binary-tree-diagram\n        private StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) {\n            if(right!=null) {\n                right.toString(new StringBuilder().append(prefix).append(isTail ? \"\u2502   \" : \"    \"), false, sb);\n            }\n            sb.append(prefix).append(isTail ? \"\u2514\u2500\u2500 \" : \"\u250c\u2500\u2500 \").append(value).append(\"\\n\");\n            if(left!=null) {\n                left.toString(new StringBuilder().append(prefix).append(isTail ? \"    \" : \"\u2502   \"), true, sb);\n            }\n            return sb;\n        }\n \n        @Override\n        public String toString() {\n            return this.toString(new StringBuilder(), true, new StringBuilder()).toString();\n        }\n    }\n\n    private BSTNode<E> root;\n\n    private BSTNode<E> search(BSTNode<E> curr, E value){\n        if (curr == null || curr.value.equals(value)) return curr;\n\n        if (value.compareTo(curr.value) > 0)\n            return search(curr.right, value);\n\n        return search(curr.left, value);\n    }\n\n    public boolean contains(E value){\n        return search(root, value) != null;\n    }\n\n    private void printInOrder(BSTNode<E> curr){\n        if (curr != null){\n            \/\/ Print left subtree\n            printInOrder(curr.left);\n            \/\/ Print curr\n            System.out.print(curr.value + \" \");\n            \/\/ Print right subtree\n            printInOrder(curr.right);\n        }\n    }\n\n    public void printInOrder(){\n        printInOrder(root);\n        System.out.println();\n    }\n\n    \/*\n    \/\/ Look-ahead version of insert. \n    private void insert(BSTNode<E> curr, E value){\n        \/\/ In look-ahead, the only way curr can be null is if it's the root. \n        if (curr == null)\n            root = new BSTNode<E>(value);\n\n        else if (value.compareTo(curr.value) > 0){\n            if (curr.right == null)\n                curr.right = new BSTNode<E>(value);\n            else \n                insert(curr.right, value);\n        }\n        else if (value.compareTo(curr.value) < 0)\n            if (curr.left == null)\n                curr.left = new BSTNode<E>(value);\n            else \n                insert(curr.left, value);\n    }\n*\/\n    \n    private BSTNode<E> insert(BSTNode<E> curr, E value){\n        if (curr == null)\n            return new BSTNode<E>(value);\n\n        if (value.compareTo(curr.value) > 0)\n            curr.right = insert(curr.right, value);\n        else if (value.compareTo(curr.value) < 0)\n            curr.left = insert(curr.left, value);\n\n        return curr;\n    }\n\n    public void insert(E value){\n        root = insert(root, value);\n        \/\/ For lookahead version:\n        \/\/insert(root, value);\n    }\n\n    @Override\n    public String toString(){\n        return root.toString();\n    }\n\n    \/\/ Test code.\n    public static void main(String[] args){\n        \n        BST<Integer> bst = new BST<>();\n        bst.insert(8);\n        bst.insert(3);\n        bst.insert(1);\n        bst.insert(6);\n        bst.insert(4);\n        bst.insert(7);\n        bst.insert(10);\n        bst.insert(14);\n        bst.insert(13);\n        System.out.println(bst);\n        System.out.println(\"9? \" + bst.contains(9));\n        System.out.println(\"7? \" + bst.contains(7));\n        bst.printInOrder();\n    }\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p class=\"lead\">public class BST{ @SuppressWarnings(&#8220;ClassCanBeStatic&#8221;) private class BSTNode{ BSTNode left, right; U value; public BSTNode(U value){ this.value = value; } \/\/ Adapted from Todd Davies answer to printing a BST on Stack Overflow. \/\/ https:\/\/stackoverflow.com\/questions\/4965335\/how-to-print-binary-tree-diagram private StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) { if(right!=null) { right.toString(new StringBuilder().append(prefix).append(isTail ? &#8220;\u2502 &#8221; : &#8221; &#8220;), false, sb); } sb.append(prefix).append(isTail ? &#8220;\u2514\u2500\u2500 &#8220;&hellip;<\/p>\n<p class=\"more-link-p\"><a class=\"btn btn-warning\" href=\"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1706,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_editorskit_title_hidden":false,"_editorskit_reading_time":0,"_editorskit_is_block_options_detached":false,"_editorskit_block_options_position":"{}","footnotes":""},"class_list":["post-2091","page","type-page","status-publish","hentry"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.7 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Binary Search Tree - Daniel R. Schlegel<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Binary Search Tree - Daniel R. Schlegel\" \/>\n<meta property=\"og:description\" content=\"public class BST{ @SuppressWarnings(&quot;ClassCanBeStatic&quot;) private class BSTNode{ BSTNode left, right; U value; public BSTNode(U value){ this.value = value; } \/\/ Adapted from Todd Davies answer to printing a BST on Stack Overflow. \/\/ https:\/\/stackoverflow.com\/questions\/4965335\/how-to-print-binary-tree-diagram private StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) { if(right!=null) { right.toString(new StringBuilder().append(prefix).append(isTail ? &quot;\u2502 &quot; : &quot; &quot;), false, sb); } sb.append(prefix).append(isTail ? &quot;\u2514\u2500\u2500 &quot;&hellip;Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/\" \/>\n<meta property=\"og:site_name\" content=\"Daniel R. Schlegel\" \/>\n<meta property=\"article:modified_time\" content=\"2018-11-19T22:09:05+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc241-fall-2018\\\/binary-search-tree\\\/\",\"url\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc241-fall-2018\\\/binary-search-tree\\\/\",\"name\":\"Binary Search Tree - Daniel R. Schlegel\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/#website\"},\"datePublished\":\"2018-11-19T22:09:04+00:00\",\"dateModified\":\"2018-11-19T22:09:05+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc241-fall-2018\\\/binary-search-tree\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc241-fall-2018\\\/binary-search-tree\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc241-fall-2018\\\/binary-search-tree\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Teaching\",\"item\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"CSC241 &#8211; Fall 2018\",\"item\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc241-fall-2018\\\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Binary Search Tree\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/#website\",\"url\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/\",\"name\":\"Daniel R. Schlegel\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Binary Search Tree - Daniel R. Schlegel","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/","og_locale":"en_US","og_type":"article","og_title":"Binary Search Tree - Daniel R. Schlegel","og_description":"public class BST{ @SuppressWarnings(\"ClassCanBeStatic\") private class BSTNode{ BSTNode left, right; U value; public BSTNode(U value){ this.value = value; } \/\/ Adapted from Todd Davies answer to printing a BST on Stack Overflow. \/\/ https:\/\/stackoverflow.com\/questions\/4965335\/how-to-print-binary-tree-diagram private StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) { if(right!=null) { right.toString(new StringBuilder().append(prefix).append(isTail ? \"\u2502 \" : \" \"), false, sb); } sb.append(prefix).append(isTail ? \"\u2514\u2500\u2500 \"&hellip;Read more","og_url":"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/","og_site_name":"Daniel R. Schlegel","article_modified_time":"2018-11-19T22:09:05+00:00","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/","url":"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/","name":"Binary Search Tree - Daniel R. Schlegel","isPartOf":{"@id":"https:\/\/danielschlegel.org\/wp\/#website"},"datePublished":"2018-11-19T22:09:04+00:00","dateModified":"2018-11-19T22:09:05+00:00","breadcrumb":{"@id":"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/binary-search-tree\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/danielschlegel.org\/wp\/"},{"@type":"ListItem","position":2,"name":"Teaching","item":"https:\/\/danielschlegel.org\/wp\/teaching\/"},{"@type":"ListItem","position":3,"name":"CSC241 &#8211; Fall 2018","item":"https:\/\/danielschlegel.org\/wp\/teaching\/csc241-fall-2018\/"},{"@type":"ListItem","position":4,"name":"Binary Search Tree"}]},{"@type":"WebSite","@id":"https:\/\/danielschlegel.org\/wp\/#website","url":"https:\/\/danielschlegel.org\/wp\/","name":"Daniel R. Schlegel","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/danielschlegel.org\/wp\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/P83Tb6-xJ","_links":{"self":[{"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/2091","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/comments?post=2091"}],"version-history":[{"count":1,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/2091\/revisions"}],"predecessor-version":[{"id":2092,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/2091\/revisions\/2092"}],"up":[{"embeddable":true,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/1706"}],"wp:attachment":[{"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/media?parent=2091"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}