Trees

a data structure that is constructed with nodes, where each has some value and may point to child-nodes, which recursively form subtrees in the tree.

The first node in a tree is called a root, some nodes on the bottom of the tree may not have child-nodes, and they are referred to as leaf nodes or just leaves.
The height of a tree is the length of its longest branch. Branches are paths between the root and its leaves.
The depth of a tree node is a distance from its tree’s root, it’s also known as a node’s level in the tree.

A tree is basically a graph that’s connected and acyclic, that has an explicit root node, and whose nodes all have a single parent (except a root node which has no parent). You may find out more about graphs here In most of the implementations nodes do not have a pointer to their parent, but they can if it’s desired.

There are many types of trees, like binary trees, heaps, AVL and more.

• Binary Tree

A tree whose elements have at most two children nodes.

The structure of a binary tree is such that many of its operations have a logarithmic time complexity, making the binary tree an incredibly attractive and commonly used data structure. This logarithmic complexity holds for balanced binary trees: whenever we choose one child-node we effectively discard the other half of the remaining nodes. If the tree is unbalanced, operations may degrade to O(n) in the worst case.

Read more about logarithms here.

• K-ary Tree

A tree whose nodes have up to k child-nodes. A binary tree is a k-ary tree where k==2.

• Complete Binary Tree

A Binary Tree that’s almost perfect. It’s a tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left. All the leaf elements must be as far left as possible.

• Perfect Binary Tree

A Binary Tree whose interior nodes all have two child-nodes whose leaf nodes all have the same depth. Example:

• Balanced Binary Tree

A Binary Tree whose nodes all have left and right subtrees whose heights differ by no more than 1.

A balanced binary tree is such that the logarithmic time complexity of its operations is maintained.

Inserting a node at the bottom of the following imbalanced binary tree right subtree would clearly not be a logarithmic time operation, since it would involve traversing through most tree nodes.

• Full Binary Tree

A Binary Tree whose nodes all have either two child-nodes or zero child-nodes.

Binary Search Tree (BST)

The most common tree variant is the Binary Search Tree. A BST is a binary tree where for every node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater. This ordering property allows for efficient searching: at each node, I can decide whether to go left or right, eliminating half the remaining nodes (in a balanced tree).

Self-Balancing Trees

Plain BSTs can become unbalanced over time (e.g., inserting sorted data produces a degenerate tree that behaves like a linked list). Self-balancing trees solve this problem by automatically restructuring themselves during insertions and deletions.

• AVL Tree – the first self-balancing BST ever invented. It maintains the invariant that the heights of the left and right subtrees of every node differ by at most 1. After each insertion or deletion, rotations are performed to restore this balance. AVL trees provide strictly balanced structure, making lookups very fast, but insertions and deletions can be slightly more expensive due to the frequent rotations.

• Red-Black Tree – a self-balancing BST where each node carries an extra bit of information: a color (red or black). A set of coloring rules ensures that the tree remains approximately balanced – no path from root to a leaf is more than twice as long as any other. Red-Black trees allow slightly less strict balancing than AVL trees, which means lookups can be marginally slower, but insertions and deletions are generally faster because fewer rotations are needed. Java’s TreeMap and TreeSet use Red-Black trees internally.

Tree Traversals

There are several standard ways to visit all nodes in a tree:

• Inorder (Left, Root, Right) – visits nodes in ascending order for a BST.
• Preorder (Root, Left, Right) – visits the root before its subtrees; useful for creating a copy of the tree.
• Postorder (Left, Right, Root) – visits the root after its subtrees; useful for deleting a tree or evaluating expression trees.
• Level-order (BFS) – visits nodes level by level from top to bottom.

You can find detailed implementations of these traversals in my Depth First Search in Java post.

Complexity of Common Tree Operations

Operation	BST (average)	BST (worst case)	Balanced BST (AVL / Red-Black)
Search	O(log n)	O(n)	O(log n)
Insert	O(log n)	O(n)	O(log n)
Delete	O(log n)	O(n)	O(log n)

The worst case for a plain BST occurs when the tree degenerates into a linear chain (e.g., inserting already-sorted data). Self-balancing trees guarantee O(log n) for all three operations regardless of the insertion order.