DSA in Java: Trees & Binary Search Trees (Beginner Guide)

So far our data structures have been "linear" — arrays, lists, stacks, queues all lay items in a line. Now we branch out, literally. A tree is a hierarchical structure, like a family tree or a folder system, and the Binary Search Tree (BST) is one of the most elegant ideas in all of DSA. Trees also unlock recursion's full power — they're where recursion truly shines.

What is a tree?

A tree is made of nodes connected in a parent-child hierarchy. It starts at a single root node at the top, and each node can have children below it. Nodes with no children are called leaves. You've seen trees in real life constantly: file folders, org charts, comment threads, the HTML of a web page.

A binary tree is a tree where each node has at most two children, called left and right. In Java, a tree node looks a lot like the linked-list node from before, but with two pointers instead of one:

class TreeNode {
    int value;
    TreeNode left;      // left child (or null)
    TreeNode right;     // right child (or null)

    TreeNode(int value) { this.value = value; }
}

The Binary Search Tree (BST): order with a rule

A BST is a binary tree with one beautiful rule that makes it powerful:

Look back at the diagram: 50 is the root; 30 (smaller) is left, 70 (larger) is right; under 30, we have 20 (smaller) left and 40 (larger) right. That ordering is what makes searching fast — it's binary search in tree form!

Searching a BST

To find a value, start at the root and go left or right based on the comparison — halving the tree each step, just like binary search. On a balanced BST that's O(log n):

boolean search(TreeNode node, int target) {
    if (node == null) return false;      // fell off the tree — not found
    if (node.value == target) return true;  // found it
    if (target < node.value)
        return search(node.left, target);   // smaller → go left
    else
        return search(node.right, target);  // larger → go right
}

Notice how naturally recursion fits: the same function, called on a smaller subtree. This is why trees are the perfect place to get comfortable with recursion.

Tree traversals: visiting every node

Often you need to visit all nodes. The most useful is the in-order traversal — go left, visit the node, then go right. On a BST, this magically visits the values in sorted order:

void inOrder(TreeNode node) {
    if (node == null) return;   // base case
    inOrder(node.left);              // 1. left subtree
    System.out.println(node.value);  // 2. this node
    inOrder(node.right);             // 3. right subtree
}
// On our example tree, prints: 20, 30, 40, 50, 70, 80 — sorted!

There are three traversal orders worth knowing by name: in-order (left, node, right → sorted for a BST), pre-order (node first — good for copying a tree), and post-order (node last — good for deleting a tree). They're the same recursion with the "visit" line moved.

Why balance matters

A BST's O(log n) speed assumes it's reasonably balanced. If you insert already-sorted data, the tree degenerates into a straight line (basically a linked list!) and search drops to O(n). Real libraries solve this with self-balancing trees (Red-Black trees) — and that's exactly what Java's TreeMap and TreeSet use under the hood. So in practice you get sorted, O(log n) structures for free.

Trees were the moment DSA got genuinely fun for me. After grinding through linear structures, seeing a problem branch into subtrees — and watching a three-line recursive function elegantly handle the whole thing — felt like a superpower. My tip: always start your tree functions with the base case if (node == null) return ..., then trust recursion to handle the left and right subtrees. Almost every tree problem follows that shape. Draw small trees on paper and trace the traversals by hand; once the recursion clicks here, graphs (next up) will feel like a natural extension.

Key takeaways

• A tree is a hierarchy of nodes with a root at top; a binary tree gives each node up to two children (left/right).
• A BST keeps smaller values left, larger values right — enabling O(log n) search on a balanced tree.
• In-order traversal of a BST visits values in sorted order; pre/post-order are the same recursion reordered.
• Unbalanced BSTs degrade to O(n); Java's TreeMap/TreeSet use self-balancing trees to stay fast.

← Previous: DSA Lesson 9 — Hashing
Next: DSA Lesson 11 — Heaps & Priority Queues →
↑ Back to the DSA roadmap