The shape: nodes, children, and leaves
A binary tree is a set of nodes connected top-down. One node is the root. Each node stores a value and has up to two links — a left child and a right child — either of which can be empty. Nodes with no children are called leaves. Think of a family tree, a tournament bracket, or the folders on your computer: structure that branches downward.
A few terms recur everywhere. A node's parent is the node directly above it, and its subtree is itself plus everything beneath it. Depth is how many edges separate a node from the root; height is the number of edges on the longest path from a node down to a leaf. These two numbers largely determine how fast tree operations run.
Traversals: four ways to visit every node
To do anything useful you have to walk the tree. Three depth-first orders differ only in when you handle the current node relative to its children: preorder (node, then left, then right), inorder (left, node, right), and postorder (left, right, node). Each is a three-line recursion built around the same base case: an empty node does nothing.
The fourth order, level-order (breadth-first), visits the tree row by row using a queue. The order you choose isn't arbitrary — inorder on a BST emits values in sorted order, preorder is handy for copying or serializing a tree, postorder suits freeing nodes or evaluating expression trees, and level-order handles anything 'closest first.' Watching the pointer move through each order step by step is usually the moment it clicks.
Binary search trees, height, and balance
A binary search tree (BST) adds one rule: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. That invariant lets you search like a phone book — compare, then go left or right — discarding half the remaining nodes at each step.
Because you follow a single root-to-leaf path, search, insert, and delete cost O(h), where h is the height. A balanced tree keeps h near log n, giving O(log n). But insert values in already-sorted order and the tree degenerates into a straight chain: h = n, and every operation slows to O(n). Self-balancing variants like AVL and red-black trees rearrange nodes as you go to guarantee logarithmic height.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder(node):
"""Left, node, right — yields BST values in sorted order."""
if node is None:
return []
return inorder(node.left) + [node.value] + inorder(node.right)
def height(node):
"""Edges on the longest root-to-leaf path; empty tree is -1."""
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))In a balanced tree h ≈ log n, so BST operations are O(log n) on average. A degenerate tree — for example inserting sorted values — collapses into a chain, making h = n and operations O(n) in the worst case.
When to use it
- When your data is naturally hierarchical — file systems, org charts, the HTML DOM, or decision trees.
- When you need ordered keys with fast search, insert, and delete together, as in the map or set behind many standard libraries (a balanced BST).
- When parsing or evaluating structured input, such as expression trees or abstract syntax trees.
- When you want sorted iteration or range queries for free — an inorder walk of a BST returns keys in ascending order.
Watch out for
- Confusing a binary tree with a binary search tree. A plain binary tree has no ordering guarantee; only a BST maintains left < node < right, and only then does search become logarithmic.
- Assuming O(log n) always holds. An unbalanced BST — classically from inserting already-sorted data — degrades into a linked list with O(n) operations. Reach for a self-balancing tree when you need guarantees.
- Forgetting the empty-node base case in recursion, or mixing up height and depth. Deep recursion on a skewed tree can also overflow the call stack.
Trees are one of the most heavily tested interview topics, and most questions are variations on a few patterns: implement the traversals both recursively and iteratively, print a tree level by level with a queue, validate that a tree is a BST, compute height or diameter, find the lowest common ancestor, or check whether a tree is balanced or symmetric. Interviewers are watching for clean recursion with a correct base case, the instinct to reach for a stack or queue when an iterative solution is asked for, and an honest complexity analysis that distinguishes the balanced case from the O(n) skewed worst case. Being able to explain your recursive structure out loud matters as much as the final code.