Trees

        88
      /    \
    60      93
   /  \    /  \
  43   67 70   99
 /  \         /
10   22     96

      60
    /    \
  43      67
 /  \
10   22

    43
  /    \
10      22

      93
    /    \
  70      99
 /
96

Continuing down the left side of this tree:

    70
  /
96

        88
      /    \
    60      93
   /  \    /  \
  43   67 70   99
 /  \         /
10   22     96

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

# Creating a tree at the root
root = TreeNode(88)

# Populate the left subtree
root.left = Tree(60)
root.left.left = Tree(43)
root.left.right = Tree(67)
root.left.left.left = Tree(10)
root.left.left.left.right = Tree(22)

# Populate the right subtree
root.right = TreeNode(93)
root.right.left = TreeNode(91)
root.right.right = TreeNode(99)
root.right.right.right = TreeNode(101)

{
    "value": 88,
    "left": {
        "value": 60,
        "left": {
            "value": 43,
            "left": {
                "value": 10,
                "left": None,
                "right": None
            },
            "right": {
                "value": 22,
                "left": None,
                "right": None
            }
        },
        "right": {
            "value": 67,
            "left": None,
            "right": None
        }
    },
    "right": {
        "value": 93,
        "left": {
            "value": 91,
            "left": None,
            "right": None
        },
        "right": {
            "value": 99,
            "left": None,
            "right": {
                "value": 101,
                "left": None,
                "right": None
            }
        }
    }
}

        88
      /    \
    60      93
   /  \    /  \
  43   67 91   99
 /  \            \
10   22           101

def in_order_traversal_iterative(root):
    result = []
    stack = []
    current = root

    while current or stack:
        # Reach the leftmost node of the current subtree
        while current:
            stack.append(current)
            current = current.left

        # Current is now None, pop from stack and visit
        current = stack.pop()
        result.append(current.value)

        # Now visit right subtree
        current = current.right

    return result

def in_order_traversal(tree):
    if tree is None:
        return []
    return in_order_traversal(tree.left) + [tree.value] + in_order_traversal(tree.right)
```javascript

I’m just gonna leave that there and let you ponder it, but we’ll come back to this idea in chapter 11.

### Insertion

Inserting a node into a tree involves first finding the correct location an a new node and then adding it to the tree. This process is very similar to inserting a node into a heap, as was shown in Chapter 7. There one big difference is that in a heap the new node is always added to the bottom of the heap tree, which is then restructured to maintain the heap. In a binary search tree, both steps are accomplished at the same time new nodes are added at the top (root) and then moved into place.

\<ILLUSTRATION OF INSERTION TK\>

Here is a function that can be used to build the binary search tree we’ve been discussing in this chapter:

``` python
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        # Create a new node
        new_node = TreeNode(value)

        # If there is no root, the tree is empty,
        # so set the new node as the root
        if self.root is None:
            self.root = new_node
            return

        # Start inserting at the root
        current = self.root

        # Climb down the tree until the correct
        # position is found for the new node
        while True:
            # If the value is less than the root, go left
            if value < current.value:
                # If there is no left child, this must be the place
                # to insert the new node
                if current.left is None:
                    current.left = new_node
                    return
                # Otherwise, move to the left child
                current = current.left

            # Same process again for the right child
            elif value > current.value:
                # If there's no right child, then this must be the place
                # to insert the new node
                if current.right is None:
                    current.right = new_node
                    return
                # Otherwise, move to the right child
                current = current.right

            # Otherwise the value is already in the tree,
            # and we have sworn to ignore duplicates
            # so we can just return
            else:
                return

    # Print the BST nodes in sorted order
    # using in-order traversal as discussed above
    def in_order_traversal(self):
        result = []
        stack = []
        current = self.root

        while current or stack:
            while current:
                stack.append(current)
                current = current.left

            current = stack.pop()
            result.append(current.value)

            current = current.right

        return result

bst = BinarySearchTree()

# Try moving the numbers around, or adding new ones, you'll always get a tree!
values = [88, 60, 43, 10, 22, 67, 93, 91, 99, 101]
for value in values:
    bst.insert(value)

# Test the in-order traversal (should print sorted values)
print(bst.in_order_traversal())

def delete_leaf_node(node):
    if node is None:
        return None
    if node.left is None and node.right is None:
        return None
    return node
```javascript

Case two is a wee bit trickier, but not by much. If the node to be deleted only has one child, then the child can simple be moved up to take the place of the parent. All of the other children will remain in place, and balance will be restored to the kingdom. This can be accomplished with a function like this:

``` python
def delete_node_with_one_child(node):
    if node is None:
        return None
    if node.left is None:
        return node.right
    if node.right is None:
        return node.left
    return node
```javascript

The third case presents a bit of a challenge. What to do if the node to be deleted has two children. If that’s the case then a lot of nodes need to move up. But there’s a simple trick that can be used to solve the problem easily. When the parent is deleted either the left child or the right child needs to be moved up to take its place. This can be done by either finding the largest value in the left child, or the smallest value in the right child, moving it up to become the parent.

This is a bit of a tricky operation, but it can be with the help of a function that finds the largest value in a treeL

``` python
def find_largest_value(node):
    if node is None:
        return None
    while node.right is not None:
        node = node.right
    return node.value
```javascript

With that function in place, the node is ready to be swapped out and deleted:

``` python
def delete_node_with_two_children(node):
    if node is None:
        return None
    if node.left is None and node.right is None:
        return None
    if node.left is not None and node.right is not None:
        # Find the largest value in the left child
        largest_value = find_largest_value(node.left)
        # Move it up to take the place of the parent
        node.value = largest_value
        # Delete the original parent
        node.left = delete_node_with_one_child(node.left)
    return node
```python

### Balancing

Something I was confused about what I first got started with trees is the idea that something in the algorithm needs to "balance" the tree. Like, I don’t want to end up with a tree that looks like this:

            88
          /
        60
       /
      43
     /
    10

This is more of a linked list than a tree, right? Maybe 60 should be at the root, with 88 as its right child. How can I prevent such a thing from happening?

The great thing about BSTs is that they are self-balancing. All of the rules that go into creating a BST also ensure that the tree stays balanced. This might not be true for every kind of tree, but it is true for BSTs. So keep calm, and rip trees.

> **If Trees are so great, why don’t programming languages already have them?**
>
> Excellent question!
>
> There are a few "native" trees in some programming languages, like Java’s `TreeSet` and `TreeMap` or `set` and `map` in the C++ Standard Template Library, but most programming languages do not have a native implementation of trees.
>
> The reason, I suspect, is simple. Most trees are created for a very specific purpose, like the DOM in a web browser or the file system on your computer.
>
> Because of the need for such specific functions and data, a more generic tree implementation would likely have to be modified to work with specific sets of data, or would be difficult to optimize for specific use cases.
>
> In other words: pretty useless.
>
> That doesn’t mean they’re not important, though. It just means that if you get to the point where you’re sure you need a tree, it will also be crystal clear to you exactly what it needs and how to build your own. Good thing the rules for creating trees are so simple!

## Tries

Tries (rhymes with "fries") are a type of tree that is used to store strings. They are used in applications like spell checkers and autocomplete, and are a great way to store a large number of strings in a way that is easy to search.

Unlike all of the trees we’ve discussed so far, tries are not binary trees. A single node in a trie can have multiple children, and the nodes are not necessarily ordered in any specific way.

\<Image of trie TK\>

The structure of a trie is determined by the strings that are stored in it. This makes them great for creating relationships between small pieces of data, like letters in a word. This makes them highly applicable to problems like spell checking and autocomplete, and they are also used extensively in natural language processing. The same things that make tries great for string manipulation make them not-so-great for larger types of data, and you would certainly not want to use them for databases or graphics processing.

If you want to build your own custom auto-complete algorithm for your web site, surely a trie library will be involved. Here is a very basic example of a trie in Python:

    class TrieNode:
        def __init__(self):
            self.children = {}
            self.is_end_of_word = False

In this example each "node" of the tree is represented by a `TrieNode` object. This object contains a dictionary of children, which allows for multiple children for node. It also contains a boolean value that indicates whether or not the node is the end of a word. In this way it bears some resemblance to a linked list, but with multiple children for each node. This allows for the strings stored in a trie to be easily searched and manipulated.

    class Trie:
        def __init__(self):
            self.root = TrieNode()

        def insert(self, word):
            current = self.root

            # Traverse the trie character by character
            for char in word:
                if char not in current.children:
                    current.children[char] = TrieNode()
                current = current.children[char]

            # Mark the end of the word
            current.is_end_of_word = True

        def search(self, word):
            current = self.root

            # Traverse the trie character by character
            # If character doesn't exist, word is not in trie
            for char in word:
                if char not in current.children:
                    return False
                current = current.children[char]

            # Return True if we've reached the end of a word
            return current.is_end_of_word

Here each word is inserted into the tree one character at a time, with each character being a node in the tree. Bear in mind that the variable names "char," "word," and "children" are just variable names. They could be anything. There’s no special reserved trie magic in Python.

\<Image of trie node TK\>

Tries will store words one character at a time, with words that share starting characters sharing nodes in the tree. The words "stamp," "stand," and "start" would all share the same starting nodes of "st." "Stamp" and "stand" would share the "sta" node, and "start" would have its own "star" node — which it would share with "stare" and "startle," should they be added to the trie.

Here are some helper functions that can be added to the already defined `Trie` class that it can use to find words based on their starting characters:

``` python
    def starts_with(self, prefix):
        current = self.root

        # Traverse the trie character by character
        for char in prefix:
            if char not in current.children:
                return False
            current = current.children[char]

        return True

    def get_suggestions(self, prefix):
        suggestions = []
        current = self.root

        for char in prefix:
            if char not in current.children:
                return suggestions
            current = current.children[char]

        # Collect all words starting from this node
        self._collect_words(current, prefix, suggestions)
        return suggestions

    def _collect_words(self, node, prefix, suggestions):
        if node.is_end_of_word:
            suggestions.append(prefix)

        for char, child_node in node.children.items():
            self._collect_words(child_node, prefix + char, suggestions)
```python

Play around with this code and add some print statements and see if you can get it to work as an autocomplete algorithm. This code is most of the way there, and shouldn’t require too much tinkering to get it to work. Another idea is to add a function that visualizes the trie, so you can see how it works. Last of all, how would you delete a word from a trie? We will return to tries in Chapter 12, so it will be worth your time to play around with them now.

## Other Types of Trees

The intended target audience for this book is likely either only going to be asked about trees in the more general way in which I’ve already described then, or they’ll already have domain-specific knowledge of the trees that can be used to solve specific problems. So I’m only going to cover a few of the more common tree types generally, and I encourage you go online or use AI if you want to learn more about them.

### B-Trees

B-Trees can be used to store data that is easy to search, update, and delete. The defining characteristic of a B-Tree is that it is a self-balancing tree that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

### Red and Black Trees

Red and black trees are similar to the binary search trees described in this chapter, with a few added rules to help keep them balanced. Red and black trees are primarily used in places where data is being constantly added and removed, like a database or file system.

In a red and black tree, it should not surprised you to find that either node is — wait for it! — red or black. Because of these additional rules, red and black trees are more self balancing than binary search trees

### AVL Trees

AVL trees are another type of self-balancing binary search tree. The work similarly to red and black trees and are also used with data that requires a lot of addition and deletion, but contain a different set of rules that balance them. AVL trees are primarily concerned with the height of the tree, and will balance by spreading out nodes to keep the tree from getting too tall. This might seem like a silly thing, but because trees can generally be searched in O(log n) time, the smaller the n, the faster the search.

## Example Questions

### Balancing trees

I said earlier in the chapter that binary search trees are self-balancing, but that’s a bit of an oversimplification two reasons. First of all, binary search trees are only self-balancing if they’re constructed in a way that maintains the self-balancing properties. This construction has to extend to the insertion and deletion of nodes, and all that might entail in terms of moving nodes around. The second reason is that I chose binary search trees because they’re both widely used and also because they’re among the easiest trees to construct and understand.

While not only binary search trees but other types of trees like red and black trees and AVL trees are self-balancing, there are other types of trees that are not. My first question for you is: Why? What could the possible advantage be to using a tree that is not self-balancing?

My second question is: How would you go about balancing a tree that is not self-balancing, should it be required? This is a concept that’s been covered in one way way or another in earlier chapters, and so I’m going not going to provide the answer here.

The hint I’ll give it to consider the chapter on heaps and the upcoming chapter on graphs. If you’re still stuck, have a look at the AI section at the end of this chapter and see if what’s suggested there can help you come up with a solution.

### Finding height of tree

Write an algorithm to find the height of a binary tree. This one sounds complicated, but it’s actually pretty simple. Remember that the height of a tree is the number of edges from the root node to the furthest leaf node. I recommend you try to write it yourself before looking at the solution below, but I’ll give you a hint: the solution uses recursion.

``` python
def find_height(node):
    if node is None:
        return -1  # Return -1 for null nodes to count edges correctly
    left_height = find_height(node.left)
    right_height = find_height(node.right)
    return 1 + max(left_height, right_height)