Tree traversal

The method to visit all the nodes in a tree is called tree traversal. This can be done either depth-first search (DFS) or breadth-first search (BFS). We will discuss these two methods in the subsequent subsections.

Depth-first traversal

In depth-first traversal, we traverse the tree, starting from the root, and go deeper into the tree as much as possible on each child, and then continue to traverse to the next sibling. We use the recursive approach for tree traversal. There are three forms of depth-first traversal, namely, in-order, pre-order, and post-order.

In-order traversal and infix notation

...