Tree Depth-first Search: Introduction

Let’s understand the Tree Depth-first Search pattern, its real-world applications, and some problems we can solve with it.

Overview

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.

We know that a tree is a data structure that can have values of any data type and is made up of nodes, connected by edges. However, what sets a tree apart from other data structures, such as an array or linked list, is that multiple ways exist to explore it. Tree depth-first search is a method to reduce the use of nested loops in our tree-related problems. Depth-first search in a tree is usually implemented recursively. However, it can also be implemented iteratively with the help of a stack. The fundamental characteristic of this pattern is that it travels as far as possible along each tree branch before exploring the others.

There are three main methods to solving a problem with the depth-first search pattern—Preorder, Inorder, and Postorder. We’ll take a look at each of them briefly and talk about how they are used—and more importantly, where they are used:

  • Preorder traversal: The preorder traverses the tree in the following three steps:

    • Visit the root node
    • Recursively perform preorder traversal on the left child
    • Recursively perform preorder traversal on the right child

In preorder traversal, we start by visiting the root of the tree itself and then traverse our tree by first exploring all the branches on the left side until we reach their deepest nodes, and then repeating the process for the nodes on the right side of our root.

The meaning of visit depends on the application. If we are calculating the size in bytes of the directory structure on a disk, for example, this may involve accumulating the size of the files in a particular directory.

  • Inorder traversal: The inorder tree traversal explores the tree in the following three steps:

    • Recursively perform inorder traversal on the left child
    • Visit the node
    • Recursively perform inorder traversal on the right child

Inorder traversal means that we move from the leftmost element to the rightmost element in our tree. In other words, we would start traversing our tree from the left first, before exploring the right side of the tree. This variation of depth-first search is usually used when we have to find elements that are smaller than the root in a binary search tree.

  • Postorder traversal: The postorder traversal explores the tree in the following three steps:

    • Recursively perform postorder traversal on the left child
    • Recursively perform postorder traversal on the right child
    • Visit the node

It works by going to the deepest node on the left side of the tree and storing that node. If a node does not have a left child, it goes to the right child and visits it. Finally, it visits the parent node.

Imagine deleting a tree. If we use preorder traversal and delete the root node, first, we would lose the pointers to the left and right subtrees and wouldn’t be able to delete those. That’s a memory leak. If we use inorder traversal and delete the left child followed by the root, the right subtree couldn’t be deleted. If we use the postorder traversal and delete the root node after deleting both the subtrees, then we get the desired result.

We can take a look at how each of these methods works in the example below:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.