Everything you need to know about Tree Traversal Algorithms: Theory and Practice in Java
Originally published by Sylvain Saurel on April 9th 2019 In computer science, a Tree is a widely used abstract data type (ADT), or data structure implementing this ADT, that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root. Thanks to Wikipedia for that great definition of Tree data structure in computer science. Tree sample Trees can be traversed in several ways: Pre Order Traversal: Root, Left, Right.In our example: A B D H I E J C F G K In Order Traversal: Left, Root, Right. In our example: H D I B J E A F C K G Post Order Traversal: Left, Right, Root. In our example: H I D J E B F K G C A Level Order Traversal, also known as Breadth-first search. In our example: A B C D E F G H I J K In that tutorial, you are going to learn how to implement these different Tree Traversal Algorithms in Java with recursion and without recursion. Like you could see, recursion solutions are easier than iterative ones. But, you need to understand both solutions because implementing these algorithms are often asked in coding interviews. For our examples, we will use Java programming language but the logic would be the same for implementing in other languages like C or Python. Representing a Tree First step is to represent a Tree. A Tree has nodes. So, we start by defining a Node class. A Node will have the following properties: data representing data of the node left pointer pointing to the left node right pointer pointing to the right node It gives us the following Node class: For representing a Tree, we will just have to choose a Node instance as root of the tree. It gives us the following code for the Tree building: Tree Pre Order Traversal with Recursion We start by implementing the Tree Pre Order Traversal Algorithm with Recursion. We want to traverse each node of the tree by displaying data for Root, Left and Right node. So, we need to define a recursive preOrderTraverse method taking a Node in parameter and making the following operations: Displaying data Calling preOrderTraverse for the left node Calling preOrderTraverse for the right node It gives us the following implementation: You can discover the implementation and the execution of the Tree Pre Order Traversal Algorithm with Recursion in video on YouTube: Tree Pre Order Traversal with Iterative solution Now, things are getting a little more complicated as we will implement with a Tree Pre Order Traversal Algorithm with an Iterative solution. For that, we will need a Stack of Node. » Read More
Like to keep reading?
This article first appeared on hackernoon.com. If you'd like to keep reading, follow the white rabbit.