Binary tree traversal means that all nodes in the binary tree are visited in a certain order starting from the root node, so that each node is visited once and only once.

There are three common traversal methods in binary tree traversal: pre-order traversal, middle-order traversal and post-order traversal. Next, I will try to use three sets of animations to introduce the logical thinking of these three traversal modes in detail to the readers, hoping that any binary tree can be quickly delineated in their mind.

The premise

Before introducing these three sets of animations, we will use diagrams to introduce the creation of binary trees and some conventions in animations.

As shown in the figure, a node in a binary tree has left and right subtrees. Through two green connecting lines, this node is divided into three regions, which are represented by the three auxiliary points, namely, front, middle and back.

These three points indicate when to retrieve the value of this node in a binary tree traversal.

Each node is traversed in the order of front – left green line – center – right green line – back.

The former sequence traversal

The specific process of using recursion to realize the preorder traversal is as follows:

  • Start by accessing the root node
  • Walk through the left subtree again in order
  • Finally, sequence traverses the right subtree

Let’s give a full explanation of the above animation to understand the recursive implementation of the preceding traversal.

  • First visited28This node, let’s seeBefore the auxiliary point, since it is a pre-order traversal, we fetch the value of the node at this moment28
  • Then access via the green line on the left28The left subtree
  • in16In this node, let’s seeBefore the auxiliary point, and fetch the value of the node because it is pre-traversal16
  • Access via the green line on the left16The left subtree
  • in13In this node, let’s seeBefore the auxiliary point, and fetch the value of the node because it is pre-traversal13
  • 13The left subtree of this node is empty, so we don’t have the left green line, and lookThe auxiliary point, because it is a pre-order traversal, no processing is done
  • 13The right subtree of this node is empty, so we don’t have the right green line, and let’s seeAfter the auxiliary point, because it is a pre-order traversal, no processing is done
  • And then go back to16In this node, lookThe auxiliary point, because it is a pre-order traversal, no processing is done
  • And then see16The right subtree of this node22This node, lookBefore the auxiliary point, and fetch the value of the node because it is pre-traversal22
  • .

Code implementation:

In the sequence traversal

The specific process of sequential traversal in recursive mode is as follows:

  • The left subtree is traversed in middle order
  • Then visit the root node
  • Finally, the middle order traverses the right subtree

Let’s give a full explanation of the above animation to understand the recursive implementation of middle order traversal.

  • First visited28This node, let’s seeBefore the auxiliary pointBecause it is a middle-order traversal, no processing is done
  • Then access via the green line on the left28The left subtree
  • in16In this node, let’s seeBefore the auxiliary pointBecause it is a middle-order traversal, no processing is done
  • Access via the green line on the left16The left subtree
  • in13In this node, let’s seeBefore the auxiliary pointBecause it is a middle-order traversal, no processing is done
  • 13The left subtree of this node is empty, so we don’t have the left green line, and lookThe auxiliary pointBecause it is a middle-order traversal, the value of the node is taken out13
  • 13The right subtree of this node is empty, so we don’t have the right green line, and let’s seeAfter the auxiliary pointBecause it is a middle-order traversal, no processing is done
  • And then go back to16In this node, lookThe auxiliary pointBecause it is a middle-order traversal, the value of the node is taken out16
  • And then see16The right subtree of this node22This node, lookBefore the auxiliary pointBecause it is a middle-order traversal, no processing is done
  • seeThe auxiliary pointBecause it is a middle-order traversal, the value of the node is taken out22
  • .

Code implementation:

After the sequence traversal

The specific process of sequential traversal after recursive implementation is as follows:

  • Traverses the left subtree sequentially
  • Then walk through the right subtree in order
  • Finally, access the root node

Let’s give a full explanation of the above animation to understand the recursive implementation of post-order traversal.

  • First visited28This node, let’s seeBefore the auxiliary pointBecause it is a post-order traversal, no processing is done
  • Then access via the green line on the left28The left subtree
  • in16In this node, let’s seeBefore the auxiliary pointBecause it is a post-order traversal, no processing is done
  • Access via the green line on the left16The left subtree
  • in13In this node, let’s seeBefore the auxiliary pointBecause it is a post-order traversal, no processing is done
  • 13The left subtree of this node is empty, so we don’t have the left green line, and lookThe auxiliary pointBecause it is a post-order traversal, no processing is done
  • 13The right subtree of this node is empty, so we don’t have the right green line, and let’s seeAfter the auxiliary point, fetch the value of the node because it is a back-order traversal13
  • And then go back to16In this node, lookThe auxiliary pointBecause it is a post-order traversal, no processing is done
  • And then see16The right subtree of this node22This node, lookBefore the auxiliary pointBecause it is a middle-order traversal, no processing is done
  • seeThe auxiliary pointBecause it is a post-order traversal, no processing is done
  • seeAfter the auxiliary point, fetch the value of the node because it is a back-order traversal16
  • .

Code implementation:

Welcome to: