Middle – order traversal of binary tree

Sequential traversal: root left and right

1. Accessing the root node
2. Preemptive traversal of the left subtree of the root node
3. Preemptive traversal of the right subtree of the root node

Non-recursive version of the code implementation

const bt = {
    val: 50.left: {
      val: 10.left: {
        val: 5.left: null.right: null,},right: {
        val: 15.left: null.right: null,}},right: {
      val: 70.left: {
        val: 60.left: null.right: null,},right: {
        val: 80.left: null.right: null,}}};const preorder = (root) = > {
    if(! root) {return; }
    const stack = [root];
    while (stack.length) {
        const n = stack.pop();
        console.log(n.val);
        if (n.right) stack.push(n.right);
        if(n.left) stack.push(n.left); }};// 50 10 5 15 70 60 80 

preorder(bt);
Copy the code

Middle order traversal: left root right

1. Middle order traversal of the left subtree of the root node
2. Accessing the root node
3. Middle order traversal is performed on the right subtree of the root node

Non-recursive version of the code implementation

const bt = {
    val: 56.left: {
      val: 22.left: {
        val: 10.left: null.right: null,},right: {
        val: 30.left: null.right: null,}},right: {
      val: 81.left: {
        val: 77.left: null.right: null,},right: {
        val: 92.left: null.right: null,}}};const inorder = (root) = > {
    if(! root) {return; }
    const 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; }};// 10 22 30 56 77 81 92

inorder(bt);
Copy the code

​

Post-order traversal: left and right roots

1. A post-order traversal of the left subtree of the root node is performed
2. A post-order traversal is performed on the right subtree of the root node
3. Accessing the root node

Non-recursive version of the code implementation

const bt = {
    val: 23.left: {
      val: 16.left: {
        val: 3.left: null.right: null,},right: {
        val: 22.left: null.right: null,}},right: {
      val: 45.left: {
        val: 37.left: null.right: null,},right: {
        val: 99.left: null.right: null,}}};const postorder = (root) = > {
    if(! root) {return; }
    const outputStack = [];
    const stack = [root];
    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); }}; postorder(bt);Copy the code