One Pager Cheat Sheet

• Write a function to traverse a binary tree in-order and print the value of each node while it passes, while meeting the specified complexity requirements.
• In-order traversal visits the left child nodes first, followed by the root, and then the right child, and is useful for obtaining ascending sorted order inBSTs.
• Preorder traversal can be used to create a copy of the tree or to get expressions from an expression tree (equivalent to Depth First Search (DFS)) by displaying the root's data and then traversing its left and right subtrees.
• With post-order traversal, display(root.data) will be called after traversing both left and right subtrees of the root node, which is useful for certain operations like tree deletion.
• The worst case time complexity for a recursive tree traversal is O(n), and the corresponding space complexity is on average O(logn) (balanced binary tree) and O(n) (skewed binary tree).

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function inorderTraversal(root) {

  let res = [];

  helper(root, res);

  return res;

}

​

function helper(root, res) {

  if (root) {

    if (root.left) {

      helper(root.left, res);

    }

​

    res.push(root.val);

​

    if (root.right) {

      helper(root.right, res);

    }

  }

}

​

function Node(val) {

  this.val = val;

  this.left = null;

  this.right = null;

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.