A tree is a hierarchical data structure made of nodes connected by lines called edges. It starts with a single root node at the top, and each node can have zero or more child nodes beneath it, which creates distinct levels. Trees don't contain any cycles, so there's only one path from the root to any other node. That property makes trees a natural fit for representing hierarchy, like file systems or family trees, and for efficient searching.

Tree operations behave very differently depending on how the tree is shaped. In a balanced tree, inserting, deleting, and searching usually take O(log n) time, where n is the number of nodes. We get to skip whole subtrees as we descend, which is what makes this fast. In an unbalanced tree, the same operations can degrade to O(n) in the worst case because we may have to walk every node. Here are the common operations on a balanced binary tree:

The O(log n) complexity in balanced binary trees comes from their structure. At the root, we have access to every node. Each level down halves the number of nodes we still need to consider, from n to n/2. The number of times you can halve n before reaching 1 is literally the definition of log₂(n). Because we quickly focus on a small portion of the tree with each step, many tree operations end up logarithmic.

A binary tree is a hierarchical data structure where each tree node can have up to two children: a left child and a right child. There are two core rules:

The performance of binary tree operations depends heavily on balance. In a balanced tree, search, insert, and delete typically run in O(log n), where n is the number of nodes. In the worst case (a completely unbalanced tree), those operations degrade to O(n).

A Binary Search Tree (BST) is a binary tree with one extra rule: for every tree node, all values in its left subtree are smaller, and all values in its right subtree are larger than the node's own value. That rule applies to every node, which gives the tree an ordered structure. The order is what makes searching, inserting, and deleting fast.

Because BSTs are ordered, search, insert, and delete typically run in O(log n) time on average, where n is the number of nodes. BSTs also support in-order traversal, which visits nodes in ascending order. This is handy for sorting and similar tasks:

One thing to keep in mind: these O(log n) times are the average case. In the worst case, when the tree becomes unbalanced or skewed, the operations degrade to O(n), basically a linked list. Self-balancing trees like AVL and Red-Black were built to keep the tree balanced and the operations at O(log n).

The depth of a node in a binary tree is the number of edges from the root to that node. Put simply, it's how many steps it takes to get from the top of the tree to that node. The root has a depth of 0, its immediate children have a depth of 1, and so on. The depth increases by 1 at each level as you move down the tree.

The height of a binary tree is the number of edges on the longest path from the root to a leaf. It's the longest journey from the top of the tree down to a leaf. A tree with a single node has a height of 0, while an empty tree is usually defined to have a height of -1. The height of the tree is equal to the maximum depth of any node in the tree.

# Definition for a binary tree node
class TreeNode:
    def __init__(self, val: int = 0, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # Base case: If there is no root, just return 0
        if not root:
            return 0
        
        # Setting up DFS on tree
        def dfs(root: Optional[TreeNode]) -> int:
            # Base case: If root doesn't exist, then return 0
            if not root:
                return 0
            
            left = dfs(root.left)
            right = dfs(root.right)

            return max(left, right) + 1
        
        # Call the DFS function
        return dfs(root)

Calculating the depth and height uses a post-order traversal. We start at the bottom of the tree and work upward. For each node, we find the maximum depth of its left and right children, then add 1 to account for the current node. As we move up, the depth at each node grows, and by the time we reach the root we've found the maximum depth (which is the height of the tree).

The diameter of a binary tree is the number of nodes on the longest path between any two nodes in the tree. That path may or may not pass through the root. Put another way: it's the longest distance between any two nodes. For a tree with a single node, the diameter is 1. For an empty tree, it's usually defined as 0.

# Definition for a binary tree node
class TreeNode:
    def __init__(self, val: int = 0, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # Set up nonlocal variable res to store answer
        res = 0

        # Setting up DFS on binary tree
        def dfs(root: Optional[TreeNode]) -> int:
            # Base case: If there is no root, then return 0
            if not root:
                return 0
            
            # DFS function calls for left and right children
            left = dfs(root.left)
            right = dfs(root.right)

            # If value of left + right children is greater, update res
            nonlocal res
            if (left + right) > res:
                res = (left + right)

            return 1 + max(left, right)
        
        # Call DFS function to store answer in res
        dfs(root)
        return res

To find the diameter, we need to find the two nodes that are farthest apart, so we use a post-order traversal. Our recursivefunction tracks two values at each node: the height of the current subtree and the longest diameter we've seen so far. At each node, the candidate path length is the sum of the left and right subtree heights plus 1 for the current node. This finds the diameter in a single pass and examines all possible paths without revisiting any nodes.

Trees show up everywhere: hierarchical data, search problems, recursive algorithms, and more. Here are a few tips for working with them well:

Trees are where recursion really clicks. Most of these problems are short to write but force you to think about what each recursive call should return. Work through them to internalize the patterns for traversal, BST invariants, path-aggregation, and tree DP: