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)

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.

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)

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:

    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.

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