Detailed explanation of binary tree traversal in JS

A binary tree is composed of a root node, a left subtree, and a right subtree. The left subtree and the friend subtree are each a binary tree.
This article mainly implements binary tree traversal in JS.

An example of a binary tree

var tree = {
 value: 1,
 left: {
  value: 2,
  left: {
   value: 4
  }
 },
 right: {
  value: 3,
  left: {
   value: 5,
   left: {
    value: 7
   },
   right: {
    value: 8
   }
  },
  right: {
   value: 6
  }
 }
}

Breadth-first traversal

Breadth Priority traversal starts from the first level (root node) of the binary tree and traverses level by level from top to bottom; in the same level, nodes are visited one by one in order from left to right.

Implementation:

Use an array to simulate a queue. First put the root node into the queue. When the queue is not empty, execute a loop: take out a node from the queue, and if the left subtree of the node is not empty, put the left subtree of the node into the queue; if the right subtree of the node is If it is not empty, put the right subtree of the node into the queue.
(The description is a bit unclear, just look at the code.)

var levelOrderTraversal = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var que = []
 que.push(node) 
 while(que.length !== 0) {
  node = que.shift()  
  console.log(node.value)  
  if(node.left) que.push(node.left)  
  if(node.right) que.push(node.right)
 }
}

Recursive traversal

I feel like using these letters There are three good ways to express recursive traversal:
D: visit the root node, L: traverse the left subtree of the root node, R: traverse the right subtree of the root node.
Pre-order traversal: DLR
In-order traversal: LDR
Post-order traversal: LRD
Following the meaning of the letters, it is traversal. In order ^ ^

These three types of traversal are all recursive traversals, or depth-first traversal (Depth-First Search, DFS), because it always
first accesses deeper.

Recursive algorithm for pre-order traversal:

var preOrder = function (node) { 
 if (node) {  
  console.log(node.value);
  preOrder(node.left);
  preOrder(node.right);
 }
}

Recursive algorithm for in-order traversal:

var inOrder = function (node) { 
 if (node) {
  inOrder(node.left);  
  console.log(node.value);
  inOrder(node.right);
 }
}

Recursive algorithm for post-order traversal:

var postOrder = function (node) { 
 if (node) {
  postOrder(node.left);
  postOrder(node.right);  
  console.log(node.value);
 }
}

Non-recursive depth-first traversal

In fact, for I’m not sure who these concepts belong to. Some books only talk about the above three recursive traversals for binary tree traversal. Some are divided into two types: breadth-first traversal and depth-first traversal, and recursive traversal is divided into depth traversal; some are divided into two types: recursive traversal and non-recursive traversal. Non-recursive traversal includes breadth-first traversal and the following traversal. Personally, it doesn’t matter how you divide it, as long as you master the methods and uses:)

What I just used in breadth-first traversal is a queue. Correspondingly, in this non-recursive depth-first traversal, we use a stack . Still use an array to simulate it in JS.
Here we only talk about preorder:
Well, I tried to describe this algorithm, but it was not clear. Just follow the code and you will understand.

var preOrderUnRecur = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var stack = []
 stack.push(node) 
 while(stack.length !== 0) {
  node = stack.pop()  
  console.log(node.value)  
  if(node.right) stack.push(node.right)  
  if(node.left) stack.push(node.left)
 }
}

After reading this article, I found the non-recursive post-order algorithm, so I will complete the non-recursive traversal method here.

Non-recursive in-order

First push the left node of the number onto the stack, then take it out, and then push the right node.

var inOrderUnRecur = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var stack = [] 
 while(stack.length !== 0 || node) {  
  if(node) {
   stack.push(node)
   node = node.left
  } else {
   node = stack.pop()   
   console.log(node.value)
   node = node.right
  }
 }
}

Non-recursive post-order (using a stack)

A temporary variable is used here to record the last push/pop node. The idea is to first push the root node and the left tree onto the stack, then take out the left tree, then push into the right tree, take them out, and finally take the following node.

var posOrderUnRecur = function(node) { 
 if(!node) {  
  throw new Error('Empty Tree')
 } 
 var stack = []
 stack.push(node) 
 var tmp = null
 while(stack.length !== 0) {
  tmp = stack[stack.length - 1]  
  if(tmp.left && node !== tmp.left && node !== tmp.right) {
   stack.push(tmp.left)
  } else if(tmp.right && node !== tmp.right) {
   stack.push(tmp.right)
  } else {   
   console.log(stack.pop().value)
   node = tmp
  }
 }
}

Non-recursive post-order (using two stacks)

The idea of ​​​​this algorithm is similar to the one above, s1 is a bit like a Temporary variables.

var posOrderUnRecur = function(node) { 
 if(node) {  
  var s1 = []  
  var s2 = []
  s1.push(node)  
  while(s1.length !== 0) {
   node = s1.pop()
   s2.push(node)   
   if(node.left) {
    s1.push(node.left)
   }   
   if(node.right) {
    s1.push(node.right)
   }
  }  
  while(s2.length !== 0) {   
   console.log(s2.pop().value);
  }
 }
}

Morris traversal

This method implements three depth traversals without recursion or stack, and the space complexity is O(1 ) (I am not particularly clear about this concept)
(I will leave these three algorithms aside and study them when I have time)

Morris order:

var morrisPre = function(head) { 
 if(!head) {  
  return
 } 
 var cur1 = head,
   cur2 = null
 while(cur1) {
  cur2 = cur1.left  
  if(cur2) {   
   while(cur2.right && cur2.right != cur1) {
    cur2 = cur2.right
   }   
   if(!cur2.right) {
    cur2.right = cur1    
    console.log(cur1.value)
    cur1 = cur1.left    
    continue
   } else {
    cur2.right = null
   }
  } else {   
    console.log(cur1.value)
  }
  cur1 = cur1.right
 }
}

Morris mid-order:

var morrisIn = function(head) { 
 if(!head) {  
  return
 } 
 var cur1 = head,
   cur2 = null
 while(cur1) {
  cur2 = cur1.left  
  if(cur2) {   
   while(cur2.right && cur2.right !== cur1) {
    cur2 = cur2.right
   }   
   if(!cur2.right) {
    cur2.right = cur1
    cur1 = cur1.left    
    continue
   } else {
    cur2.right = null
   }
  }  
  console.log(cur1.value)
  cur1 = cur1.right
 }
}

Morris post-order:

var morrisPost = function(head) { 
 if(!head) {  
  return
 } 
 var cur1 = head,
   cur2 = null
 while(cur1) {
  cur2 = cur1.left  
  if(cur2) {   
   while(cur2.right && cur2.right !== cur1) {
    cur2 = cur2.right
   }   
   if(!cur2.right) {
    cur2.right = cur1
    cur1 = cur1.left    
    continue
   } else {
    cur2.right = null
    printEdge(cur1.left)
   }
  }
  cur1 = cur1.right
 }
 printEdge(head)
}
var printEdge = function(head) {

That’s it I hope the entire content of this article will be helpful to everyone’s learning. For more related tutorials, please visit JavaScript Video Tutorial!