Everything you need to know about Tree Traversal Algorithms: Theory and Practice in Java

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: : Root, Left, Right.In our example: A B D H I E J C F G K Pre Order Traversal : Left, Root, Right.In our example: H D I B J E A F C K G In Order Traversal : Left, Right, Root.In our example: H I D J E B F K G C A Post Order Traversal , also known as Breadth-first search.In our example: A B C D E F G H I J K Level Order Traversal 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 class. A Node will have the following properties: Node representing data of the node data pointer pointing to the left node left pointer pointing to the right node right It gives us the following class: Node https://medium.com/media/1b1b6f819233ac87ae33440ca0fb5242/href For representing a Tree, we will just have to choose a instance as root of the tree. It gives us the following code for the Tree building: Node https://medium.com/media/907ec7dd8b5e33492c8e94540356ea35/href 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 method taking a in parameter and making the following operations: preOrderTraverse Node Displaying data Calling for the left node preOrderTraverse Calling for the right node preOrderTraverse It gives us the following implementation: https://medium.com/media/fa05d4c5d7f36c00e35b1099eea8b9e8/href You can discover the implementation and the execution of the in video on YouTube: Tree Pre Order Traversal Algorithm with Recursion 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 of . Stack Node First, we will push the Tree root in the . Then, we will iterate while the won’t be empty. We pop all nodes one by one and for each node, we make the following steps: Stack Stack Displaying data Pushing its right child in the Stack Pushing its left child in the Stack It gives us the following implementation: https://medium.com/media/82422b5b4dec25b36fd07c215b2613a2/href You can discover the implementation and the execution of the in video on YouTube: Tree Pre Order Traversal Algorithm with Iterative solution Tree In Order Traversal with Recursion We implement the Tree In Order Traversal Algorithm with Recursion. We want to traverse each node of the tree starting with Left node, displaying data for Root and finishing with Right node. So, we need to define a recursive method taking a in parameter and making the following operations: inOrderTraverse Node Calling for the left node inOrderTraverse Displaying data Calling for the right node inOrderTraverse It gives us the following implementation: https://medium.com/media/d6246a378c4c1b3abcc35e6b9c09097c/href You can discover the implementation and the execution of the in video on YouTube: Tree In Order Traversal Algorithm with Recursion Tree In Order Traversal with Iterative solution Now, things are getting a little more complicated as we will implement with a Tree In Order Traversal Algorithm with an Iterative solution. We are going to use a of . We traverse the Tree while the current node is not null or the of is not empty. Stack Node Stack Node At each iteration, we try to reach the most left node from the current node. During this nested ireration, we add each node traversed in the of . At the end of this iteration, current node is null. So, we pop a from the and we display its data. Finally, Now, we visit the right subtree. Stack Node Node Stack It gives us the following implementation: https://medium.com/media/155600f9bcf22e39d791077143863494/href You can discover the implementation and the execution of the in video on YouTube: Tree In Order Traversal Algorithm with Iterative solution Tree Post Order Traversal with Recursion We implement the Tree Post Order Traversal Algorithm with Recursion. We want to traverse each node of the tree starting with Left node, continuing with Right Node and then displaying data for Root. So, we need to define a recursive post_OrderTraverse_ method taking a in parameter and making the following operations: Node Calling post_OrderTraverse_ for the left node Calling post_OrderTraverse_ for the right node Displaying data It gives us the following implementation: https://medium.com/media/db77e4c2012aae952e14123685576a01/href You can discover the implementation and the execution of the in video on YouTube: Tree Post Order Traversal Algorithm with Recursion Tree Post Order Traversal with Iterative solution Now, things are getting a little more complicated as we will implement with a Tree Post Order Traversal Algorithm with an Iterative solution. We start by creating two of which will name nodeStack1 and nodeStack2. We push the Tree root in the nodeStack1. Stack Node We iterate while the first stack is not empty. At each iteration, we pop an item from nodeStack1 and we push it to nodeStack2. Then, we push left and right children of popped item to nodeStack1. Then, in a second loop, we print data all the elements of nodeStack2 . This gives us the following code: https://medium.com/media/f050806575583551ec13b5dce2ed2690/href You can discover the implementation and the execution of the in video on YouTube: Tree Post Order Traversal Algorithm with Iterative solution Tree Level Order Traversal Finally, we are going to implement Tree Level Order Traversal Algorithm. This algorithm is also known as Breadth-First Search. We need to use an Iterative solution. The solution uses a of . We add the Tree root. Queue Node Then, we iterate while is not empty. We dequeue a node and we print the data. Then, we add children nodes if not null, left in first and right in second. Queue It gives us the following implementation: https://medium.com/media/dec241c17c27463d2b34246acc7d63c7/href You can discover the implementation and the execution of the in video on YouTube: Tree Level Order Traversal Algorithm Conclusion This article will have allowed you to discover the main Algorithms for Tree Traversal with their implementation in Java. The complete source of the Tree class with the main method calling all the methods presented is available just below: https://medium.com/media/b0eb2ac6e4730dfb22e3f69f0cc00999/href To discover more tutorials, don’t hesitate to visit the SSaurel’s Channel on YouTube: Sylvain Saurel If you want to discover some books to learn Java programming, I advice you to read the following article with my selection of the Top 6 Best Books for Java programming : Top 6 Best Books for learning Java Programming