Trees & Binary Search Trees

Concept

A binary tree node has at most two children. Traversals: preorder (root, left, right), inorder (left, root, right), postorder (left, right, root) and level order (BFS).

In a Binary Search Tree, left subtree < node < right subtree, so inorder traversal gives sorted order and search is O(h).

Most tree problems are solved by asking: what do I need from my left and right child?

Complexity

Code (Python)

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def inorder(root, out):
    if root:
        inorder(root.left, out)
        out.append(root.val)
        inorder(root.right, out)
    return out

Remember

• Recursion fits trees naturally.
• Level-by-level → BFS with a queue.
• Validate BST with min/max bounds, not just parent.