# (1) recursive traversal of binary tree

The deep traversal binary tree is realized by using the stack stack when the system performs function call. The recursive version of binary tree is relatively simple. To implement preorder, middle order, and post order, you only need to print the tree information before, during, and after the execution of the sub-function. The code is as follows:

## The first order

```
function iterator (tree) {
if(! tree) {return
}
console.log(tree.val)
iterator(tree.left)
iterator(tree.right)
}
Copy the code
```

## In the sequence

```
function iterator (tree) {
if(! tree) {return
}
iterator(tree.left)
console.log(tree.val)
iterator(tree.right)
}
Copy the code
```

## After the order

```
function iterator (tree) {
if(! tree) {return
}
iterator(tree.left)
iterator(tree.right)
console.log(tree.val)
}
Copy the code
```

**Summary: Time complexity :O(n), space complexity :O(h), h is the height of the tree**

# (2) binary tree iterative traversal

## The first order

Sequential traversal of binary trees (head => left => right), implemented by iteration. Ideas:

- Use a stack to store the tree node
- Continuously pop a node from the stack, print the node (print the head node, then operate the child node, that is, first traversal, the order is: head => left => right)
- Add the right node and the left node of the pop-up node to the stack in turn (because it is a stack, last in first out, so add the right child first, then add the left child node. The next loop prints the left child first, then the right.)

```
// start traversal (head left to right)
function iterator (tree) {
let stack = [tree]
while (stack.length) {
tree = stack.pop()
console.log(tree.val)
tree.right && (stack.push(tree.right))
tree.left && (stack.push(tree.left))
}
}
Copy the code
```

## In the sequence

Backorder traversal of binary tree (left => head => right), implemented by iteration. Ideas:

- All the left children of the tree are added to the stack in turn until the leaf node is traversed
- Eject the node and print it
- Moving the pointer right continues to add all the left children of the pop-up node to the stack

```
// Middle order traversal (left head right)
function iterator (tree) {
let stack = [tree]
while (stack.length) {
if (tree.left) {
stack.push(tree.left)
tree = tree.left
continue
}
tree = stack.pop()
console.log(tree.val)
if (tree.right) {
tree = tree.right
stack.push(tree)
}
}
}
Copy the code
```

## After the order

Backorder traversal of binary trees (left => right => head), implemented iteratively, requires an additional auxiliary stack. Ideas:

- Use a stack to store the tree node
- Constantly popping a node from the stack and adding it to the secondary stack (adding the head node to the secondary stack first)
- Add the left node and the right node of the pop-up node to the stack in turn (the right node and the left node will be added to the secondary stack in turn in the next two cycles)
- Traversal secondary stack (in secondary stack, the order of addition is head => right => left, back in first out, i.e. traversal order is left => right => head)

```
function iterator (tree) {
let stack = [tree]
let helpStack = []
while (stack.length) {
tree = stack.pop()
helpStack.push(tree)
if (tree.left) {
stack.push(tree.left)
}
if (tree.right) {
stack.push(tree.right)
}
}
while (helpStack.length) {
tree = helpStack.pop()
console.log(tree.val)
}
}
Copy the code
```

**Conclusion: Both pre-order and middle-order recursion are deep traversal, time complexity :O(n), space complexity :O(h), h is the height of the tree, post-order because of the auxiliary stack, space complexity is O(n).**

# (3) breadth-first traversal binary tree

## Sequence traversal

The sequence traversal of binary tree is realized by iteration.

- Use a queue and store it to the tree node
- Continually eject a node from the queue and print
- Add the left and right nodes of the eject nodes to the queue in turn

```
// sequence traversal
function iterator(tree) {
let queue = [tree]
while (queue.length) {
tree = queue.shift()
console.log(tree.val)
tree.left && queue.push(tree.left)
tree.right && queue.push(tree.right)
}
}
Copy the code
```

# (4) Morris traverses binary trees

## Morris traversal

Morris traversal is characterized by using the idle nodes of the leaf nodes of the tree (both the left and right Pointers are null). In the traversal process, the idle nodes of the leaf are rewritten to control the direction of the traversal, which can achieve the space complexity of O(1) and time complexity of O(n).

- If tree has no left node, the tree moves to the right (tree=tree.right).
- If the tree has a left node, find the right-most node on the left subtree of the tree and call it mostright
- If the mostright pointer is null, make it point to cur and move it to the left (tree=tree.left)
- If the mostright pointer points to cur, make it null and move it to the right (tree=tree.right).

Explain why a stack is needed for recursive and non-recursive traversal. The recursion does not explicitly use the stack, but it is essentially implemented using the stack. Since there are only Pointers from the parent node to the child node in the binary tree, what should I do if I want to return from the child node to the parent node in the traversal process? The data structure stack is used here. The parent node is pushed onto the stack first, and the child node is visited. Morris traversal also involves traversing the entire binary tree, so how does a Morris traversal go from child to parent? From the rules of Morris traversal, it can be seen that Morris traversal is from the child node to the parent node by pointing to the right child of mostRight.

```
function iterator(tree) {
let mostRight = null
while (tree) {
if (tree.left) {
mostRight = tree.left;
while(mostRight.right && mostRight.right ! == tree) { mostRight = mostRight.right; }if(! mostRight.right) {// Change the right pointer to the leaf to point to itself
mostRight.right = tree
tree = tree.left
continue
}
// Adjust the right pointer of the modified node to the original NULL
mostRight.right = null
}
tree = tree.right
}
}
Copy the code
```

In morris traversal, the node with a left child node is traversed twice, and the node with no left node is traversed only once. Preorder, middle order and post order can be overwritten according to this property.

## Morris, a first order

Precedence: For a node without a left node, the node is traversed only once. If the node is traversed, the node is printed. For a node with a left child node, it is traversed twice and printed by the first traversal machine (the rightmost node of the left tree of this node is empty).

```
function iterator(tree) {
let mostRight = null
while (tree) {
if (tree.left) {
mostRight = tree.left;
while(mostRight.right && mostRight.right ! == tree) { mostRight = mostRight.right; }if(! mostRight.right) {console.log(tree.val)
mostRight.right = tree
tree = tree.left
continue
}
mostRight.right = null
} else {
console.log(tree.val)
}
tree = tree.right
}
}
Copy the code
```

## Morris in sequence

Middle order: For a node without a left node, the node is traversed only once. If the node is traversed, the node is printed. For a node with a left child node, it is traversed twice, and the second traversal is printed by the diachronic machine (the right-most node of the left tree of the node points to itself).

```
// morris in order traversal
function iterator(tree) {
let mostRight = null
while (tree) {
if (tree.left) {
mostRight = tree.left;
while(mostRight.right && mostRight.right ! == tree) { mostRight = mostRight.right; }if(! mostRight.right) { mostRight.right = tree tree = tree.leftcontinue
} else {
console.log(tree.val)
mostRight.right = null}}else {
console.log(tree.val)
}
tree = tree.right
}
}
Copy the code
```

## Morris, after the order

After the sequence:

- For nodes with no left subtree, the nodes are traversed only once, and you don’t care about the nodes.
- For nodes with left subtrees, the nodes are traversed twice, printing the right edge of the left subtree in reverse order during the second traversal.
- Finally, just before the function exits, print the right edge of the entire tree in reverse order.

In order to reverse print the right boundary of the tree without applying extra space (the method of extra space: collect the right boundary with the stack, and then print the stack), it can be associated with the flip of a linked list. After flipping the right pointer of the node, it can reverse print, and then adjust the point back. As shown in figure:

```
// morris after traversal
function iterator(tree) {
// Invert the tree (right pointer)
function reverseTree(tree) {
let pre = null
let next = null
let cur = tree
while (cur) {
next = cur.right
cur.right = pre
pre = cur
cur = next
}
return pre
}
function operateTree (tree) {
let cur
// Invert the right margin first
tree = reverseTree(tree)
cur = tree
// Prints the flipped node
while (cur) {
console.log(cur.val)
cur = cur.right
}
// Reverse the tree to the original order
reverseTree(tree)
}
let cur = tree
let mostRight = null
while (tree) {
if (tree.left) {
mostRight = tree.left;
while(mostRight.right && mostRight.right ! == tree) { mostRight = mostRight.right; }if(! mostRight.right) { mostRight.right = tree tree = tree.leftcontinue
} else {
mostRight.right = null
operateTree(tree.left)
}
}
tree = tree.right
}
operateTree(cur)
}
Copy the code
```