# Binary Trees {% hint style="success" %} "The most important concept in computer science" - Josh Hug {% endhint %} ## Humble Origins Linked lists are great, but we can do better! Let's try **rearranging the pointers** in an interesting way. Instead of starting at one end of the list, let's set our first pointer at the **middle** of the list! ![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M75vZl9f32dnvtTW21B%2F-M762cLhT3bPorFJckAb%2Fimage.png?alt=media\&token=bb1fb648-46ea-44f2-a139-61fb00e36c37) Now, let's make new pointers going to the **center** of each **sublist** on the left and right of the center. ![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M75vZl9f32dnvtTW21B%2F-M762lJvyxizprpX4UQk%2Fimage.png?alt=media\&token=b43bf804-97fa-4d15-9159-a00c6a1ce1ab) Let's do it again! ![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M75vZl9f32dnvtTW21B%2F-M762pguD51u2ZiSsItP%2Fimage.png?alt=media\&token=ee598f92-67cb-4191-8ec2-9595e4fedd35) Would ya look at that, we've got a **tree**! 🌲 ![🌲🌲🌲🌲🌲](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M75vZl9f32dnvtTW21B%2F-M7632bGF984CbCkTISY%2Fimage.png?alt=media\&token=3eb58965-2c8b-44ac-9fc2-1f2d42552bcb) ## Types of Trees Right now, we can determine some properties that all trees have. * All trees have a **root node**. * All nodes can point to **child nodes.** Or, if they don't have any children, they are **leaves.** We can add more and more constraints to our tree to make them more useful! First, let's add the constraint that **node can only have 2 or fewer children** to create a **binary tree.** Then, let's **ensure our tree is sorted** to create a **binary search tree.** A tree is sorted if it has these properties: * Every value in the **left subtree** of a node is **less than** the node's value. * Every value in the **right subtree** of a node is **greater than** the node's value. * Values are **transitive** - there are **no duplicate values**. * The tree is **complete** - it is possible to **compare any two values** in the tree and say that one is **either less than or greater than the other.** * The tree is **antisymmetric** - If `p < q` is true and `q < r` is also true, then it must follow that `p < r`. ## Tree Operations There are **three important operations** that trees should support: **find, insert, and delete.** ### **Find** Finding a value in a tree uses Binary Search. Click the link below to read up on it! {% content-ref url="../algorithms/searching/binary-search" %} [binary-search](https://cs61b.bencuan.me/algorithms/searching/binary-search) {% endcontent-ref %} ### Insert The insert algorithm is **very similar to binary search.** Here are the steps to take: * Search for the item. **If it's found, then do nothing** since the value is already in the tree. * If it's not found (search would return null in this case), then create a node and put it where it should be found. If using recursion, this last step is already done- all we need to do is return a new node! Here's the algorithm: ```java public BST insert(BST T, Key sk) { if (T == null) { // Create new leaf with given key. Different from search return new BST(sk, null, null); } if (sk.equals(T.key)) { return T; } else if (sk < T.key) { T.left = find(T.left, sk); // Different from search } else { T.right = find(T.right, sk); // Different from search } } ``` ### Delete This one's a bit trickier because we need to make sure that the new tree still **preserves the binary search tree structure.** That means that we might have to shuffle around nodes after the deletion. There are **three cases:** A) The node to delete is a **leaf**. This is an easy case- just remove that node and you're done! ![Deleting a leaf.](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M75vZl9f32dnvtTW21B%2F-M76-4hXjqSTouEqhcZW%2Fimage.png?alt=media\&token=90d9c00d-8aea-438c-9081-c8c8f93a1744) B) The node to delete has **one child.** In this case, **swap** the node with its child, then **delete the node.** ![Deleting a node with one child.](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M75vZl9f32dnvtTW21B%2F-M76-EJUP-gn_0we1GAg%2Fimage.png?alt=media\&token=1eddc971-92f3-4d7e-a602-6e807ca80b45) C) The node to delete has **two children.** This one's trickier, because we still need to preserve the tree structure! In this case, we have to **traverse the node's children** to find the **next biggest value** and swap that up to replace the old node. ![Deleting a node with two children.](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M75vZl9f32dnvtTW21B%2F-M76-fhnOAX3SHmO1dbt%2Fimage.png?alt=media\&token=d00ed955-7f6c-4ba5-a861-7811b66d1881) ## Asymptotic Analysis A binary tree can be **bushy** or **spindly.** These two cases have dramatically different performances! **Bushy** trees are the **best case.** A tree is bushy if **every parent has exactly 2 children.** A bushy tree is guaranteed to have a height of $$\Theta(\log(n))$$ which means that the runtimes for adding and searching will also be $$\Theta(\log(n))$$ . **Spindly** trees are the **worst case.** A tree is spindly if **every parent has exactly 1 child.** This makes the tree essentially just a linked list! A spindly tree has a height of $$\Theta(n)$$ which means that the runtimes for adding and searching will also be $$\Theta(n)$$ . ![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M75vZl9f32dnvtTW21B%2F-M761ctmUWAUmoZ1x88o%2Fimage.png?alt=media\&token=90f10388-0ce2-448b-a2f8-67aead477525) In [Balanced BSTs](https://cs61b.bencuan.me/abstract-data-types/binary-trees/balanced-search-structures), we will explore ways of guaranteeing that a tree is bushy! ## Limits of Trees While trees are extremely versatile and fantastic for a variety of applications, trees have some limitations that make it difficult to use in some situations. * **All items in a tree need to be comparable.** We can't construct a binary tree out of categorical data, like models of cars, for example. * **The data must be hierarchical.** If data can be traversed through in multiple ways, or forms loops, [Graphs](https://cs61b.bencuan.me/abstract-data-types/graphs) are probably better. * **The best case runtime is** $$\Theta(\log(n))$$ . This might seem good, but other data structures like [Tries](https://cs61b.bencuan.me/abstract-data-types/binary-trees/tries) and [Hash Tables](https://cs61b.bencuan.me/abstract-data-types/hashing) can be as good as $$\Theta(1)$$ ! ## Tree Traversals Check out these pages for information on how to go through each element of a tree! {% content-ref url="../algorithms/searching/depth-first-search-dfs" %} [depth-first-search-dfs](https://cs61b.bencuan.me/algorithms/searching/depth-first-search-dfs) {% endcontent-ref %} {% content-ref url="../algorithms/searching/breadth-first-search-bfs" %} [breadth-first-search-bfs](https://cs61b.bencuan.me/algorithms/searching/breadth-first-search-bfs) {% endcontent-ref %} --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://cs61b.bencuan.me/abstract-data-types/binary-trees.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.