# Trees

Time:

* Usually `O(n)` (visit each node)
* `O(n*k)` where k is work at each node

Space:

* `O(n)` - Straight line, all on stack
* `O(longn)` - balanced tree

Depth: `O(logn)`

## DFS

Pre-order: Operate on node on way down. (Logic before - pre)

```python
def preorder_dfs(node):
    if not node:
        return

    print(node.val)
    preorder_dfs(node.left)
    preorder_dfs(node.right)
    return
```

In an increasing tree (root < child) this gives us increasing order.

In-order: Order on the way up. (logic in middle - in)

In BST translates to in order.

Do left, then print val, then right.

```python
def inorder_dfs(node):
    if not node:
        return

    inorder_dfs(node.left)
    print(node.val)
    inorder_dfs(node.right)
    return
```

Post-order: Go to leaves before anything else. (logic after - post)

```python
def postorder_dfs(node):
    if not node:
        return

    postorder_dfs(node.left)
    postorder_dfs(node.right)
    print(node.val)
    return
```

## BFS

`O(V+E)`

(balanced tree) The final level in a perfect binary tree has n/2 nodes, so BFS uses `O(n)` space

To traverse levels, use:

```python
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        q = deque([root])
        lrg = []
        while q:
            lvl = len(q)
            for _ in range(lvl): # Traverses level
                n = q.popleft()
                if n.left is not None:
                    q.append(n.left)
                if n.right is not None:
                    q.append(n.right)

        return lrg
```

## Trie

A trie (pronounced “try”) is a tree-based data structure that stores strings efficiently by sharing common prefixes. Also called a prefix tree, a trie enables fast string search, insertion, and deletion operations in O(L) time, where L is the string length.

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

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

    def insert(self, word):
        current = self.root
        for char in word:
            if char not in current.children:
                # For each char, go down tree inserting if not present
                current.children[char] = TrieNode()

            # Add each char as a child of current
            current = current.children[char]
        current.is_end_of_word = True

    def search(self, word):
        current = self.root
        for char in word:
            if char not in current.children:
                return False
            current = current.children[char]
        return current.is_end_of_word

# Example usage
trie = Trie()
trie.insert("GLOBAL")

print(trie.search("GLOBE"))   # False
print(trie.search("GLOBES"))  # False
```


---

# 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://docs.ramsdenj.com/introduction-4/notes/trees.md?ask=<question>
```

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.