What is a tree data structure, and how is it different from a linear data structure?

A tree stores data as a hierarchy of nodes connected by edges, starting from one root, where each node has one parent and can have many children. In a linear structure such as an array or linked list, each element has at most one next element, forming a single sequence. A tree is non-linear and models hierarchies such as folders and organization charts.

What is the difference between a binary tree and a binary search tree?

Both allow at most two children per node. A binary tree has no rule about where values go, while a binary search tree keeps smaller values in the left subtree and larger values in the right subtree. As a result, searching a balanced BST takes O(log n) time, while searching a plain binary tree takes O(n).

What is the difference between the height and the depth of a node?

Depth is the number of edges from the root down to the node, so the root has depth 0. Height is the number of edges on the longest path from the node down to a leaf, so every leaf has height 0. The height of the root is the height of the tree and equals the largest depth of any node.

Why do we need self-balancing trees such as AVL and red-black trees?

A binary search tree is fast only while balanced. Inserting sorted values turns it into a chain, making operations O(n). Self-balancing trees rotate nodes after inserts and deletes to keep the height near log n, so operations stay O(log n). AVL trees balance more strictly for faster lookups, while red-black trees need fewer rotations for cheaper updates; Java's TreeMap uses a red-black tree.

Why do databases use B-trees and B+ trees instead of binary search trees?

Disk reads are slow, and a binary search tree holds one key per node, so a lookup may need 20 or more reads. A B-tree node holds many keys and children, keeping the tree short so millions of records need only 3 or 4 reads. A B+ tree also stores all data in linked leaf nodes, making range queries fast, which is why most database indexes use B+ trees.

How do you represent a binary tree node in Java?

Create a TreeNode class with an int value and two TreeNode references, left and right, where null means the child does not exist. Build a tree by creating nodes and linking them, for example root.left = new TreeNode(2).

How do you find the height of a binary tree in Java?

Use recursion: height(node) returns -1 for null, otherwise Math.max(height(node.left), height(node.right)) + 1, so a leaf has height 0 in edges. It runs in O(n) time with O(h) stack space. If height is counted in nodes, return 0 for an empty tree instead.

How do you write inorder, preorder and postorder traversals in Java?

All three visit left before right but differ in when the node is processed: inorder is left, node, right; preorder is node, left, right; postorder is left, right, node. For the sample tree they print 4 2 5 1 3, 1 2 4 5 3 and 4 5 2 3 1. Inorder of a BST gives sorted values, and each traversal is O(n).

How do you perform a level order traversal (breadth-first search) of a binary tree?

Use a queue: add the root, then repeatedly remove a node, record its value and add its left and right children to the queue. This visits the tree level by level; for the sample tree it returns [1, 2, 3, 4, 5]. It runs in O(n) time and O(w) space, where w is the maximum width.

How do you check whether a binary tree is a valid binary search tree?

Pass an allowed range down the tree: start with Long.MIN_VALUE and Long.MAX_VALUE, return false if a node's value is outside the range, then check the left subtree with the node's value as the new maximum and the right subtree with it as the new minimum. Comparing a node only with its children is not enough. It runs in O(n) time.

Tree Data Structure: Types, Terms and Operations

A tree is one of the most important non-linear data structures. It stores data in a hierarchy, much like a family tree or the folders on your computer, which makes searching, sorting and organizing data fast and natural.

In this tutorial, you will learn what a tree is, how it is represented, the key terms used with trees, the main types of trees and the common operations performed on them.

1. What Is a Tree Data Structure?

A tree is a hierarchical data structure that consists of nodes connected by edges. Each node contains a value (data) and may have zero or more child nodes. The topmost node in a tree is called the root node, and the nodes at the bottom that do not have children are called leaf nodes.

A tree is a non-linear data structure, which means the data is not stored in a sequential order. Trees organize and manage data efficiently and allow easier and faster searching and sorting of data elements.

2. Representation of a Tree

Tree data structure hierarchy with a root node, internal nodes and leaf nodes

The tree above contains 11 nodes and 10 edges.

Remember: a tree with N nodes always has exactly N - 1 edges, because every node except the root is connected to its parent by one edge.

3. Tree Terminology

Node: An entity that contains a key (data) and references to its child nodes.
Edge: The link that connects two nodes. All nodes in a tree are connected by edges.
Root Node: The first, topmost node of the tree. Every tree has exactly one root, and the root has no parent.
Parent Node: A node that has a branch to one or more other nodes (its children).
Child Node: A node that descends from another node.
Leaf Node: A node that has no children. Leaf nodes are the bottom-most nodes of the tree.
Internal Node: A node that has at least one child. All nodes other than leaf nodes are internal nodes, also known as non-terminal nodes.
Degree of a Node: The total number of children of a node. The highest degree among all nodes is called the degree of the tree.
Depth of a Node: The number of edges on the path from the root to that node. The depth of the root is 0.
Height of a Node: The number of edges on the longest path from that node down to a leaf node.
Level of a Node: The root is at level 0, its children are at level 1, their children are at level 2, and so on.
Path: The sequence of nodes and edges from one node to another. The length of a path is the number of nodes in it.
Subtree: Every child node forms a subtree under its parent node.

Learn each term in detail in the Tree Terminology tutorial.

4. Types of Trees

There are several types of trees, and each is designed to meet specific application requirements:

Let's briefly look at each type.

4.1 Binary Tree

A binary tree is a special type of tree in which every node can have at most two child nodes, called the left child and the right child.

Binary tree where each node has at most two children

In a binary tree, every node has three parts:

Data
Reference to the left child node
Reference to the right child node

4.2 Binary Search Tree (BST)

A Binary Search Tree (BST) organizes data in a tree-like structure. It has a single starting node called the root, and each node can have at most two child nodes: a left child and a right child.

In a BST, the value of each node is greater than all the values in its left subtree and less than all the values in its right subtree. This ordering property makes BSTs efficient for searching, inserting and deleting elements.

In the tree above, 50 is the root node. It has two child nodes: 30 (root of the left subtree) and 70 (root of the right subtree).

Important points of a Binary Search Tree

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
The left and right subtrees must also be binary search trees.
Duplicate keys are usually not allowed; if they are needed, they must be handled with a fixed rule.

4.3 Red-Black Tree

A red-black tree is a self-balancing binary search tree in which every node is colored either red or black. The color of each node is decided by the properties of the red-black tree.

Every node contains an extra bit that represents its color. These colors keep the tree balanced during operations such as insertion and deletion.

The red-black tree was introduced by Rudolf Bayer in 1972.

Properties of a Red-Black Tree

A red-black tree must be a binary search tree.
Every node is either red or black.
The root node is always black.
The children of a red node must be black (there are no two consecutive red nodes).
Every path from a node to its leaf nodes contains the same number of black nodes.
Every leaf node (also called a NULL or NIL node) is black.

4.4 AVL Tree

An AVL tree is a height-balanced binary search tree. A binary tree is balanced if the difference between the heights of the left and right subtrees of every node is -1, 0 or +1. Every node in an AVL tree stores this extra information, called the balance factor.

The AVL tree was introduced in 1962 by G.M. Adelson-Velsky and E.M. Landis.

In an AVL tree, the balance factor of every node is either -1, 0 or +1.

The balance factor of a node is the difference between the heights of its left and right subtrees:

Balance factor = height(left subtree) - height(right subtree)

When an insertion or deletion breaks this rule, the tree restores its balance using rotations:

AVL tree rotations used to rebalance the tree

4.5 B-Tree

In search trees such as binary search trees, AVL trees and red-black trees, every node contains only one key and at most two children. A B-tree allows a node to contain more than one key and more than two children, which makes searching, inserting and deleting records very efficient.

A B-tree is a self-balanced search tree in which every node contains multiple keys and has more than two children.

The number of keys and children a node can have depends on the order of the B-tree. Every B-tree has an order.

The B-tree was invented by Rudolf Bayer and Edward M. McCreight at Boeing Research Labs to efficiently manage index pages for large random-access files.

Key characteristics of a B-Tree

Balanced: All leaf nodes are at the same depth, which keeps access times predictable.
Multi-way nodes: Unlike binary trees, a B-tree node can have many children, limited by the order of the B-tree.
Multiple keys per node: Nodes hold more than one key, which reduces the height of the tree and the number of disk reads.
Efficient I/O: B-trees suit systems that read and write large blocks of data, such as databases and file systems.
Self-balancing updates: Insertion and deletion split or merge nodes when needed to keep the tree balanced.

4.6 B+ Tree

A B+ tree is a variation of the B-tree that supports efficient insertion, deletion and search. In a B+ tree, all the values (data) are stored in the leaf nodes, and the internal nodes are used only for indexing, like a table of contents.

All the leaf nodes are linked together, which makes it quick to read a range of values.

Features of a B+ Tree

Balanced: All leaf nodes are at the same level. After every insertion or deletion, the tree adjusts itself to stay balanced.
Data storage: The leaf nodes store the actual data (records).
Internal nodes: Internal nodes store only keys and references to child nodes.
Ordered: Keys are kept in sorted order, which makes range queries and sorted reads simple.
Minimum degree: Every internal node except the root has at least ⌈m/2⌉ children, where m is the order of the tree.
Disk-oriented: B+ trees are a common choice for databases and file systems because they keep disk reads low.
High fan-out: Each internal node can have many children, which keeps the tree short and searches fast.

5. Operations on a Tree

Insert: Add an element to the tree.
Delete: Remove an element from the tree.
Search: Find an element in the tree.
Traversal: Visit every node of the tree in a specific order:
- Preorder traversal: Each node is processed before (pre) its subtrees.
- Inorder traversal: The node is visited between its left and right subtrees.
- Postorder traversal: The node is visited after both of its subtrees.

See Tree Traversals: Inorder, Preorder and Postorder for step-by-step examples.

6. Summary

A tree is a hierarchical, non-linear data structure made of nodes connected by edges.
A tree with N nodes has N - 1 edges, and it always has exactly one root.
Binary trees and BSTs allow at most two children per node; AVL and red-black trees keep a BST balanced.
B-trees and B+ trees store many keys per node and are widely used in databases and file systems.
The common tree operations are insert, delete, search and traversal.

Help Us Improve

Tree Data Structure

1. What Is a Tree Data Structure?

2. Representation of a Tree

3. Tree Terminology

4. Types of Trees

4.1 Binary Tree

4.2 Binary Search Tree (BST)

Important points of a Binary Search Tree

4.3 Red-Black Tree

Properties of a Red-Black Tree

4.4 AVL Tree

4.5 B-Tree

Key characteristics of a B-Tree

4.6 B+ Tree

Features of a B+ Tree

5. Operations on a Tree

6. Summary

Frequently Asked Questions (FAQ)