Happy weekend, everyone! Today I want to talk about a very common interview topic — on the realization of binary tree front, middle and back order traversal. This article will implement these three traversal methods in both recursive and non-recursive ways, and the code is relatively short and can be safely eaten.

To briefly explain what’s the difference between the three traverse way – for each traversal, each node in the tree is three times (for leaf node, the left and right subtrees as a loophole tree), but the preorder traversal access immediately, when the first met node in the sequence traversal is encountered in the second node access, sequence traversal is the third time after the visit.

Therefore, the order of the nodes to be visited in front, middle and back traversal is left, right and left respectively. “Middle” represents the current node, and “left and right” represents the left and right subtrees of the current node.

Let’s take a look at how the code is implemented.

The recursive version

The former sequence traversal

 public static void preOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head.value + "");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }
Copy the code

In the sequence traversal

    public static void inOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        inOrderRecur(head.left);
        System.out.print(head.value + "");
        inOrderRecur(head.right);
    }
Copy the code

After the sequence traversal

    public static void posOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.print(head.value + "");
    }
Copy the code

The recursive version

The former sequence traversal

public static void preOrderUnRecur(Node head) {
   if(head ! = null) { Stack<Node> stack = new Stack<Node>(); stack.add(head);while(! stack.isEmpty()) { head = stack.pop(); System.out.print(head.value +"");
       if(head.right ! = null) { stack.push(head.right); }if(head.left ! = null) { stack.push(head.left); }}}}Copy the code

In the sequence traversal

public static void inOrderUnRecur(Node head) {
   if(head ! = null) { Stack<Node> stack = new Stack<Node>();while(! stack.isEmpty() || head ! = null) {if(head ! = null) { stack.push(head); head = head.left; }else {
         head = stack.pop();
         System.out.print(head.value + ""); head = head.right; }}}}Copy the code

After the sequence traversal

public static void posOrderUnRecur(Node head) {
   if(head ! = null) { Stack<Node> s1 = new Stack<Node>(); Stack<Node> s2 = new Stack<Node>(); s1.push(head);while(! s1.isEmpty()) { head = s1.pop(); s2.push(head);if(head.left ! = null) { s1.push(head.left); }if (head.right != null) {
         s1.push(head.right);
         }
     }
     while(! s2.isEmpty()) { System.out.print(s2.pop().value +""); }}}Copy the code

So these are the three ways to traverse a binary tree, have you learned it?

PS: This article was originally published on the wechat official account “More than Java”.