This article is a summary written after reading “Learning JavaSscript Data Structure and Algorithm”, mainly to remember the difficulties I met in the book, as well as some points that may not be too difficult, but will be more difficult to understand, for everyone’s reference and study, but also let myself review and consolidate. The second part of this article is combined with the interview questions.

Traversal of binary trees

First of all, we are going to build a binary tree, and then we are going to take this binary tree as an example to explain its three traversal methods, so that you can compare the differences between the three traversal methods.

Start building the binary tree shown above

const tree = new BinarySearchTree()
Tree.insert (8) // root
tree.insert(2)
tree.insert(9)
tree.insert(3)  console.log(tree) Copy the code

When it’s built, print it out and see if it’s structurally correct on the console

You can see that the structure of this tree is correct, so let’s start learning binary tree traversal

① Order traversal first

Sequential traversal (pre-sequential traversal) : Each node is accessed in precedence over subsequent nodes. Take a look at its code implementation implementation as follows:

  preOrderTraverse(callback) {
    this.preOrderTraverseNode(this.root, callback);
  }

  preOrderTraverseNode(node, callback) {
 if(node ! = null) {callback(node.key); / / {1}this.preOrderTraverseNode(node.left, callback); / / {2}this.preOrderTraverseNode(node.right, callback); / / {3} }  } Copy the code

Sequential traversal visits the node itself ({1}), then its left child ({2}), and finally its right child ({3}) : “Print itself first”, “iterate over all its children to the left, iterate over all its children to the right”, we define a callback function as follows:

const printNode = (value) => console.log(value)
Copy the code

The preceding traversal function is then executed

tree.preOrderTraverse(printNode)
Copy the code

Observe the output from the console

Why is it such an output? If you don’t get it, take a look at the “code” below (note the comments).

tree.preOrderTraverse(printNode)->

PreOrderTraverseNode (8,printNode)-> execute the {1} callback directly to print 8callback(8)
PreOrderTraverseNode (8.left,printNode)= //PreOrderTraverseNode (2,printNode)-> execute the {1} callback directly to print out 2callback(2) PreOrderTraverseNode (2. Left,printNode)-> // The traversenode (2. Left,printNode)-> preOrderTraverseNode(2. Left,printNodePreOrderTraverseNode (2.right,printNode)= // Traversenode (2PreOrderTraverseNode (3,printNode)-> execute the {1} callback directly to print out 3callback(3) PreOrderTraverseNode (3. Left,printNode)-> // Traversenode (3. Left,printNode)-PreOrderTraverseNode (3. Right,printNode)-> // Perform recursion 3. Right, but the right side of 3 is also null and the same is returnedPreOrderTraverseNode (8. Right,printNode)= // Traversenode (8PreOrderTraverseNode (9,printNode)-> execute the {1} callback directly to print 9callback(9) PreOrderTraverseNode (9. Left,printNode)-> // The traversenode (9. Left,printNode)-PreOrderTraverseNode (9. Right,printNode)-> // The recursion executes 9. Right, but the right side of 9 is also null, so it returnsCopy the code

Perform this function, the first “was introduced into the root node 8, directly will call the callback print 8”, then begins to traverse the left side of the 8, first “was introduced into 2, direct call the callback print 2”, then traverse the 2 on the left, but 2 no children to return to the left of the traverse on the right side of the 2, “incoming 3, direct callback print 3”, Traversal 3 left and right sides are no children, because the left subtree is already all traversal, returned directly to the 8, began to traverse the right of the eight “into 9, 9 direct call print”, and then traverse the right and left sides of the 9 no child nodes, and then right subtree traversal also completed, left and right subtrees are traversal is complete, function before the end of the sequence traversal is just introduced to the node, Just call the callback to print out the node, and then start traversing the left and right sides of the node. After watching the above two procedures, I believe you can understand the binary tree before traversal.

② Middle order traversal

Middle-order traversal: a method of traversal in which more than one row accesses all nodes of a binary tree sequentially, that is, all nodes are accessed in the smallest to largest order. The code implementation is as follows:

  inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
  }

  inOrderTraverseNode(node, callback) {
 if(node ! = null) {this.inOrderTraverseNode(node.left, callback); / / {1}callback(node.key); / / {2}this.inOrderTraverseNode(node.right, callback); / / {3} }  } Copy the code

The sequence traversal will first visit its left child {1}, then call the callback to print itself {2}, and finally access its right child {3}. Similarly, “in layman’s terms”, middle-order traversal is to recursively traverse all the nodes on the left, then print itself, and finally traverse all the nodes on the right. The callback function remains unchanged:

const printNode = (value) => console.log(value)
Copy the code

Call the middle-order traversal function

tree.inOrderTraverse(printNode)
Copy the code

Observe the output from the console

You can see, as I said, that the order of access is from smallest to largest, so it’s possible to sort with a binary tree, but it’s rarely done.

Once again, you can understand the execution of a middle-order traversal by looking at the “code” below:

tree.inOrderTraverse(printNode)->

InOrderTraverseNode (8,printNode)-> inOrderTraverseNode(8,printNode)-inOrderTraverseNode(8.left,printNode)=  
InOrderTraverseNode (2,printNode)-> inOrderTraverseNode(2,printNode)-InOrderTraverseNode (2. Left,printNode)-> inOrderTraverseNode(2. Left,printNode)-> nullThe left side of callback(2) //2 is traversed, the callback prints out 2, and the right side is traversedInOrderTraverseNode (2. Right,printNode)= // the right child of 2 which is passed 3InOrderTraverseNode (3,printNode)-> inOrderTraverseNode(3,printNode)-InOrderTraverseNode (3. Left,printNode)-> //3 left null, returnThe left side of callback(3) //3 is traversed, the callback prints out 3, and the right side is traversedInOrderTraverseNode (3. Right,printNode)-> // null to the right of 3, return to 8Callback (8) // The left side of 8 is already iterated, so {2} is executed to print 8InOrderTraverseNode (8. Right,printNode)= // Pass 9 to the right of 8InOrderTraverseNode (9,printNode)-> inOrderTraverseNode(9,printNode)-InOrderTraverseNode (9. Left,printNode)-> null of 9, returnCallback (9) // The left side of 9 is iterated, the callback prints 9, and the right side is iteratedInOrderTraverseNode (9. Right,printNode)-> null of 9, return. The right side of 8 is traversed, the whole binary tree is traversed, and the function is finishedCopy the code

8, perform this function, first introduced to the root node will traverse the left side of the 8 first, then introduced to 2, the incoming then will traverse the first 2 on the left, 2 on the left null returns, “2 to the left of the traversal is complete, then execute callback print 2”, then traverse the 2 right, the right of the 2 to 3, incoming 3, the left side of the incoming 3 began to traverse the 3, If the left node is null, the left node of 3 will be called back to print 3. If the right node is null, the left subtree of 8 will be called back to print 8. We pass in 9 and start iterating to the left of 9. If the left is null, we return “9 left is done, callback prints 9”, start iterating to the right of 9, right node is null, return, 8 left and right are iterated, end of function. As soon as the left side of the node is traversed, you can call the callback directly to print out the node.

③ After order traversal

Sequential traversal: accesses the descendant nodes of a node first and then the node itself. See its code implementation as follows:

  postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }

  postOrderTraverseNode(node, callback) {
 if(node ! = null) {this.postOrderTraverseNode(node.left, callback); / / {1}this.postOrderTraverseNode(node.right, callback); / / {2}callback(node.key); / / {3} }  } Copy the code

A backorder traversal will first visit the left child {1}, then the right child {2}, and finally the parent node itself {3} “in layman’s terms”. The backorder traversal will first traverse all the left nodes, then all the right nodes, and finally print itself back. The callback function remains unchanged as follows:

const printNode = (value) => console.log(value)
Copy the code

Call the post-order traversal function

tree.postOrderTraverse(printNode)
Copy the code

Observe the output from the console

Again, you can use the following “code” to understand the post-traversal process:

tree.postOrderTraverse(printNode)->

PostOrderTraverseNode (8,printNode)-postOrderTraverseNode(8.left,printNode)=
PostOrderTraverseNode (2,printNode)-> // The left node of 8 is 2, and the left node of 2 is traversedPostOrderTraverseNode (2. Left,printNode)-> //2 where the left node is nullPostOrderTraverseNode (2. Right,printNode)= // 3PostOrderTraverseNode (3,printNode)-PostOrderTraverseNode (3. Left,printNode)-> nullPostOrderTraverseNode (3. Right,printNode)-> //3The left and right sides of callback(3) //3 are iterated, the callback prints out 3, and then returnsCallback (2) // Returns to the left and right sides of 2, calls the callback to print out 2, and returnsPostOrderTraverseNode (8. Right,printNode)= // Return to left of 8 and start traversing right of 8PostOrderTraverseNode (9,printNode)-> // The right node of 8 is 9 and the left of 9 is traversed firstPostOrderTraverseNode (9. Left,printNode)-> null at left of 9PostOrderTraverseNode (9. Right,printNode)-Callback (9) // The left and right sides of 9 are iterated, the callback prints out 9, and returnsCallback (8) // Return to 8Copy the code

8 perform this function, first introduced to the root node, and then began to traverse the left side of the eight, to 8 left node 2, began to traverse the 2 on the left, 2 on the left is null, return to traverse the 2 right, the right of 2 nodes in 3, and then began to traverse the left side of the 3, 3 left node to null returns, 3 right nodes are also returns null, “So the right and left sides of the 3 traversal, began to call the callback print 3”, and then return to 2, to this, “the right and left sides of the 2 also traverse completed, so the callback print 2”, again returned to the left of the 8, 8 has completed all traversal, began to traverse the right of the 8 node 9 to 8 right, begin to traverse the left side of the 9, null returns, If the left and right sides of 9 are traversed again, the function is returned even if it is null, “the left and right sides of 9 are traversed, and the callback is printed out 9”, and then the function is returned to 8. At this point, “the left and right sides of 8 are traversed completely, and the callback is printed out 8”, the whole binary tree traversal is completed, and the function ends. As you can see, post-traversal is basically a callback to print out the node as soon as the left and right sides of the node are traversed.

(4) summary

Whether it is pre-order, mid-order or post-order traversal, there is no need to memorize, as long as you know whether the callback function is before, in the middle or after the traversal, then you can know what the traversal order is. According to the order of the function execution, you can understand the three traversal methods. And the second thing we need to understand is that all three of these traversals use recursion, it uses a recursive stack, and it executes functions from the top of the stack to the bottom of the stack and then goes back until the stack is empty.

⑤ Binary tree interview examples

Talk about a topic, is a back-end friend in the recent interview questions in the binary tree related to the topic “stem” : we use xingsheng preferred R & D team to do a binary tree, the binary tree “middle order traversal sequence” : back-end — UI — product manager — test — project manager — operation and maintenance — front-end — DBA; The “post-traversal sequence” is: UI — back end — Test — Product Manager — Operations — DBA — front end — Project Manager. “Question 1” : please draw the shape of the binary tree and write down your derivation. “Question 2” : Write the preceding traversal sequence of this binary tree. So let’s analyze the problem, because this problem is basically trying to solve problem 1, so problem 2 is pretty easy, and if you can derive the whole binary tree, it’s not easy to write a preorder traversal. So we have to derive this binary tree from the two traversal sequences given. In sequence: the back-end – UI – product manager – testing – project manager – operations – front end – after the DBA sequence: UI – backend – test – product manager – operations – the DBA – front – what is the distinguishing feature of project manager after the sequence traversal? Will be completed on either side of traversal, and then print itself, then think about the root node is always the last to output, because the root node subtree is not on the left and on the traversal is complete, not his print output, so this is the key point, so we can determine the project manager must be the root node. The characteristic of middle-order traversal is that when the left side of the traversal is finished, it prints itself. The project manager is the root node, so “after, U, production and test” on the left of the project manager are the left subtree nodes of the project manager, while “operation, before and D” on the right of the project manager are the right subtree nodes of the project manager. As shown below:

So once we’ve identified this structure, let’s first deal with the structure of the left subtree,“Middle order traversal of the left subtree“: Backend — UI — Product Manager — Testing“Post-order traversal of the left subtree“: UI – backend – test – product manager, is still the same can determine the product manager is the root node in the left subtree, because he is in the sequence traversal in the end, and then take a fancy to sequence traversal sequence, the back-end with the UI on the left side of the product manager, constitute the product manager left subtree, only test a node on the right, so the test must be directly is the product manager right node. This should look something like the following:

The two nodes, after and U, are determined equally,“Middle order traversal of the left subtree“: backend — UI,“Post-order traversal of the left subtree“: UI — the back end, so the back end is the root node here, and there are two cases

Figure 1× (not conforming to middle-order traversal)

FIG. 2√ (Accord)

The middle-order traversal in Figure 1 is U-post-production-test, which is inconsistent with the given middle-order traversal order, so the structure of Figure 2 should be correct. And then finally, there’s the right subtree, which is easy to determine, because of the right subtree“The sequential traversal order is o&M — DBA — front-end“, so the front end is the root node of the right subtree, and according to the right subtree“The middle traversal order is o&M — front-end — DBA“Then you can determine that operations forms the left node on the left side of the front end and DBA forms the right node on the right side of the front end. Therefore, the structure of the whole binary tree is finally determined as follows:

With problem 1 solved, problem 2 is easy to iterate through in the following order: Project Manager — Product Manager — Back end — UI — Test — front end — Operations — DBA. I hope that after reading, you can remember the difference between pre-order, mid-order and post-order. When we see this kind of topic in the future, we only need to find a breakthrough according to some characteristics of their traversal and we can quickly solve this kind of problem.

Later these knowledge points will be released in a new article update, if there is wrong in the article, please point out, thank you.

This article is formatted using MDNICE