Tree Depth-first Search: Introduction

About the pattern

A tree is a graph that contains the following properties:

• It is undirectedA graph with edges that do not have a specific direction assigned to them..

• It is acyclicA graph without cycles..

• It is a connected graph where any two vertices are connected by exactly one path.

• Its nodes can contain values of any data type.

The following key features set trees apart from other data structures, such as arrays or linked lists:

• They organize data in a hierarchical manner with a root node at the top and child nodes branching out from it.

• They are nonlinear, which means that the elements in a tree are not arranged sequentially but rather in a branching structure.

• The time complexity for search and insert operations in trees is typically $O(\log n)$, where $n$ is the number of elements in the tree. In contrast, the time complexity for search and insert operations in arrays and linked lists can be $O(n)$, where $n$ is the number of elements in the array or list.

• There are multiple ways to traverse them.

A naive approach to exploring the tree would be to revisit the already traversed nodes. More specifically, we start at the root node and traverse a particular branch all the way to the leaf node. Then, we start at the root node again and explore another branch. In this way, we’ll revisit many nodes over and over. This would take our time complexity to $O(n^2)$ in the worst case.

Tree depth-first search is another traversal method that explores the tree by traveling as far as possible along a branch before exploring the other branches. Because it visits each node of the tree exactly once, it guarantees a traversal in $O(n)$ time.

There are three main methods to traverse a tree with the tree depth-first search pattern—preorder, inorder, and postorder.

Preorder traversal

We start at the root node and visit it first. Then, we recursively traverse the left subtree, followed by the right subtree. This means we explore nodes in the order of root, left, and right. It’s like starting at the top of a tree and moving down, exploring branches as we go. Here are the steps required to implement this algorithm:

1. Traverse the left subtree: We recursively traverse the left subtree, starting from the root node. We visit each node in the traversal. If the left child node doesn’t exist, we move to step 2.

2. Traverse the right subtree: We repeat step 1 starting from the right child node of the current node. If the right child node doesn’t exist, we visit the current node.

3. We repeat steps 1–2 until all nodes in the tree have been visited.

The following illustration shows an example of preorder traversal: