JavaScript implements two ways of sequential traversal in binary trees

// Test data
const bt = {
    val: 1.left: {
        val: 2.left: {
            val: 4.left: null.right: null,},right: {
            val: 5.left: null.right: null,}},right: {
        val: 3.left: {
            val: 6.left: null.right: null,},right: {
            val: 7.left: null.right: null,}}};Copy the code

// Recursive
const inorder = (root) = > {
    if(! root) {return; }
    inorder(root.left);
    console.log(root.val);
    inorder(root.right);
};
Copy the code

// Non-recursive
const inorder = (root) = > {
    if(! root)return
    const stack = [] // define a stack, last in first out
    let p = root
    while(stack.length || p){ // If the stack is empty and p is empty, the tree has been traversed
        while(p){
            stack.push(p) / / into the stack
            p = p.left // Keep accessing the left subtree
        }
        const n  = stack.pop() / / out of the stack
        console.log(n.val)
        p = n.right // Access the right subtree}}Copy the code