### Front-end tree correlation algorithm

Tree traversal combines the idea of a stack

Sample code:

``````let tree = {
val: '1'.left: {
val: '2'.left: {
val: '4',},right: {
val: '3',}},right: {
val: '5'.right: {
val: '6',,}}}Copy the code``````

#### Tree depth-first traversal

``````let dfs = (root) = > {
if(! root) {return
}
consloe.log(root.val)
if (root.left) dfs(root.left)
if (root.right) dfs(root.right)
}
Copy the code``````

#### Breadth first traversal of the tree

``````let bfs = (root) = > {
if(! root) {return
}
let p = [root]
while (p.length) {
let n = p.shift()
if (n.left) p.push(n.left)
if (n.right) p.push(n.right)
}
}
Copy the code``````

#### Preemptive tree traversal (left and right root)

``````// A recursive solution
let preInorder = (root) = > {
if(! root) {return
}
console.log(root.val)
preInorder(root.left)
preInorder(root.right)
}
/ / stack method
let preInorder = (root) = > {
if(! root) {return
}
let stack = [root]
while (stack.length) {
let n = stack.pop()
console.log(n.val)
if (n.right) stack.push(n.right)
if (n.left) stack.push(n.left)
}
}
Copy the code``````

#### Middle order traversal of trees (left root right)

``````// A recursive solution
let inInorder = (root) = > {
if(! root) {return
}
inInorder(root.left)
console.log(root.val)
inInorder(root.right)
}

/ / stack method
let inInorder = (root) = > {
if(! root) {return
}
let stack = []
let p = root
while (stack.length || p) {
while (p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
console.log(n.val)
p = n.right
}
}

Copy the code``````

#### Post-order traversal of the tree (left and right roots)

``````// A recursive solution
let downInorder = (root) = > {
if(! root) {return
}
downInorder(root.left)
downInorder(root.right)
console.log(root.val)
}

/ / stack method
let downInorder = (root) = > {
if(! root) {return
}
let stack = [root]
let outputStack = []
while (stack.length) {
const n = stack.pop()
outputStack.push(n)
if (n.left) stack.push(n.left)
if (n.right) stack.push(n.right)
}
while (outputStack.length) {
const n = outputStack.pop()
console.log(n.val)
}
}
Copy the code``````