Binary tree traversal: recursion, iteration, and parent pointer

The basics of binary trees are presented, including, here . I will add my own “5 kopecks” and with this post I will systematize the materials related to the traversal of binary trees, namely comparisons of the possibilities of recursion and iterations, as well as discussing the possibilities of using a pointer to the parent node.

So ... Java language, the node class has the following form:

public class Node { Node left; Node right; Node parent; String value; public Node(Node p, String v){ parent=p; value=v; } … } 

Note : A pointer to the parent parent - usually does not make much sense, however, as follows from the title and will be shown, it can be useful in some cases.

Traversing trees - sequential processing (viewing, changing, etc.) of all nodes of the tree, in which each node is processed strictly once. This results in a linear arrangement of tree nodes.

Depending on the trajectories, there are two types of traversal:
- horizontal (wide); and
- vertical (in depth).
')
Horizontal traversal implies traversing the tree by levels (level-ordered) - all nodes of the current level are processed first, and then the transition to the lower level is performed.


During vertical traversal, the processing order of the current node and nodes of its right and left subtrees varies, and three options of vertical traversal are distinguished by this feature:
- direct (prefix, pre-ordered): vertex - left subtree - right subtree;
- reverse (infix, in-ordered): left subtree - vertex - right subtree; and
- trailing (postfix, post-ordered): left subtree - right subtree - vertex.

The bypass itself in all cases is basically the same, the order of processing differs. For the presentation of the order in which the processing of tree nodes will take place, it is convenient to follow the “bypass contour”. During a direct crawl, the node will be processed at the point to the left of the node, at the reverse from the bottom of the node and with the terminal, respectively, to the right of the node.
In other words, “being” in a certain node, we need to know whether it is necessary to process it and where to go next.

Recursion

All three variants of vertical traversal are elementarily implemented by recursive functions.

  void recPreOrder(){ treatment(); if (left!=null) left.recPreOrder(); if (right!=null) right.recPreOrder(); } void recInOrder(){ if (left!=null) left.recInOrder(); treatment(); if (right!=null) right.recInOrder(); } void recPostOrder(){ if (left!=null) left.recPostOrder(); if (right!=null) right.recPostOrder(); treatment(); } 

Recursion is extremely convenient not only when traversing, but also when building a tree, searching in a tree, and also balancing. However, recursion cannot be performed horizontal traversal of the tree. In this case, as well as with concerns about overloading the software stack, an iterative approach should be taken.

Containers

In the case of iterations, it is necessary to keep information about visited but not processed nodes. Stack-type containers (for vertical bypass) and a queue (for horizontal bypass) are used.

Horizontal Bypass:

we process the first node in the queue; if there are child nodes, we bring them to the end of the queue. Go to the next iteration.

  static void contLevelOrder(Node top){ Queue<Node> queue=new LinkedList<> (); do{ top.treatment(); if (top.left!=null) queue.add(top.left); if (top.right!=null) queue.add(top.right); if (!queue.isEmpty()) top=queue.poll(); }while (!queue.isEmpty()); } 

Vertical direct traversal:

we process the current node, in the presence of the right subtree we add it to the stack for further processing. Go to the node of the left subtree. If there is no left node, go to the top node from the stack.

  static void contPreOrder(Node top){ Stack<Node> stack = new Stack<> (); while (top!=null || !stack.empty()){ if (!stack.empty()){ top=stack.pop(); } while (top!=null){ top.treatment(); if (top.right!=null) stack.push(top.right); top=top.left; } } } 

Vertical reverse bypass:

from the current node we “go down” to the lowest left node, adding all the visited nodes to the stack. We process the top node from the stack. If the current node has a right subtree, we start the next iteration with the right node. If there is no right node, skip the descent step and proceed to processing the next node from the stack.

  static void contInOrder(Node top){ Stack<Node> stack = new Stack<> (); while (top!=null || !stack.empty()){ if (!stack.empty()){ top=stack.pop(); top.treatment(); if (top.right!=null) top=top.right; else top=null; } while (top!=null){ stack.push(top); top=top.left; } } } 

Vertical end round:

Here the situation becomes more complicated - unlike the reverse roundabout, besides the descent order, you need to know whether the right subtree has already been processed. One solution is to add a flag to each instance of the node that would store the relevant information (not considered). Another approach is “encoding” directly in the stack order — during descent, if the next node needs to process the right subtree later, the sequence “parent, right node, parent” is added to the stack. Thus, when processing nodes from the stack, we can determine if we need to process the right subtree.

  static void contPostOrder(Node top){ Stack<Node> stack = new Stack<> (); while (top!=null || !stack.empty()){ if (!stack.empty()){ top=stack.pop(); if (!stack.empty() && top.right==stack.lastElement()){ top=stack.pop(); }else{ top.treatment(); top=null; } } while (top!=null){ stack.push(top); if (top.right!=null){ stack.push(top.right); stack.push(top); } top=top.left; } } } 

About parent pointer

Having a pointer to a parent in an instance of a class brings certain troubles when building and balancing trees. However, the ability to “walk” from an arbitrary node of the tree to any of its nodes may come in handy. All that you need to follow when “rising” to the upper level - whether they came from the right descendant or from the left.
So, using parent pointers will look like a vertical end crawl code.

  static void parentPostOrder(Node top){ boolean fromright=false; Node shuttle=top, holder; while(true){ while (fromright){ shuttle.treatment(); if (shuttle==top) return; holder=shuttle; shuttle=shuttle.parent; fromright=shuttle.right==holder; if (!fromright && shuttle.right!=null) shuttle=shuttle.right; else fromright=true; } while (shuttle.left!=null) shuttle=shuttle.left; if (shuttle.right!=null) shuttle=shuttle.right; else fromright=true; } } 

Another class of tasks that the parent pointer allows you to solve, as already mentioned, is moving inside the tree.
So, to go to the nth node in a row from the current node, without “orientation in the tree,” you would have to bypass the tree from the very beginning, to the known node, and then n-nodes. Using the same parent pointer, when going backwards through the tree, moving the steps of the nodes from the current node (start) will look like this.

  public static Node walkTheTree(Node start, int steps){ boolean fromright=true; Node shuttle=start, holder; if (shuttle.right!=null){ shuttle=shuttle.right; while (shuttle.left!=null) shuttle=shuttle.left; fromright=false; } int counter=0; do{ while (true){ if (!fromright && ++counter==steps) return shuttle; if (!fromright && shuttle.right!=null){ shuttle=shuttle.right; break; } holder=shuttle; shuttle=shuttle.parent; fromright=(holder==shuttle.right); } while (shuttle.left!=null) shuttle=shuttle.left; }while (true); } 

Note : In general, it is also required to prevent the possibility of going beyond the tree (to rise above the root node).