Trees Explained

A tree is a hierarchical data structure made of nodes connected by edges, where one node is the root and every other node has exactly one parent. Unlike a linked list, which is linear, a tree branches: a node can have several children, forming a hierarchy that mirrors things like file systems, organisation charts, and family trees.

The vocabulary of trees

A few terms unlock most discussions:

• Root — the topmost node, with no parent.
• Child — a node directly below another.
• Parent — the node directly above a child.
• Leaf — a node with no children.
• Edge — the link between a parent and a child.
• Height — the length of the longest path from the root down to a leaf.
• Depth — the distance of a node from the root.
• Subtree — any node together with all its descendants.

A tree with n nodes always has exactly n - 1 edges, because every node except the root is reached by one edge from its parent.

Binary trees

The most common variety is the binary tree, where every node has at most two children, conventionally called left and right. Binary trees are the foundation for binary search trees, heaps, and many other structures. A binary tree is balanced when its left and right subtrees stay close in height, which keeps operations fast; if it grows lopsided, it can degrade toward the O(n) behaviour of a linked list.

Traversing a tree

Visiting every node in a defined order is called traversal. The three classic depth-first traversals differ only in when they visit the current node relative to its children:

• In-order — left subtree, node, right subtree.
• Pre-order — node, left subtree, right subtree.
• Post-order — left subtree, right subtree, node.

There is also level-order (breadth-first), which visits the tree level by level using a queue.

// A binary tree node holds a value and two child links.
class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int v) { value = v; }
}

class Tree {
    // In-order traversal: left subtree, then this node, then right subtree.
    // Visits every node exactly once, so it is O(n).
    static void inOrder(TreeNode node) {
        if (node == null) return;   // base case: empty subtree
        inOrder(node.left);         // 1. recurse left
        System.out.print(node.value + " "); // 2. visit this node
        inOrder(node.right);        // 3. recurse right
    }

    public static void main(String[] args) {
        //        4
        //       / \
        //      2   6
        //     / \ / \
        //    1  3 5  7
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);

        inOrder(root); // prints: 1 2 3 4 5 6 7
    }
}

The recursion naturally follows the tree's shape. Each call handles one node and delegates its children to further calls — a clean example of how recursion and trees fit together.

Why trees matter

Trees give you hierarchy and, when balanced, fast lookups. A balanced binary search tree supports search, insert, and delete in O(log n), far better than the O(n) scan of an unsorted list. File systems, database indexes, parsers, and decision logic all lean on tree structures.

Common mistakes

• Forgetting the base case. Recursive traversal must stop at null children. Omit the if (node == null) return; and you crash with a null reference.
• Confusing height and depth. Height is measured upward from leaves to a node; depth is measured downward from the root. They are easy to swap.
• Assuming trees stay balanced. A binary tree built from sorted insertions can become a straight line, turning O(log n) operations into O(n). Self-balancing trees exist for exactly this reason.
• Mixing up traversal orders. In-order on a binary search tree yields sorted output; pre-order and post-order do not. Pick the traversal that matches your goal.
• Treating every two-child node as a search tree. A binary tree has no ordering rule. The search property is what a binary search tree adds on top.

FAQ

What is the difference between a tree and a graph? A tree is a special connected graph with no cycles and exactly one path between any two nodes. Graphs allow cycles and multiple connections.

Which traversal gives sorted order? In-order traversal of a binary search tree visits nodes in ascending order of their keys.

Keep learning

Continue with Binary Search Trees Explained, see how trees generalise into Graphs, and browse the full DSA hub.

Want to build and traverse trees with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.