Binary Tree Traversal

Time: O(n) Space: O(n)

Keywords: Binary Tree

This is not the only way to traverse a binary tree but due to the recursive nature of trees, I feel that the best way to traverse trees is with recursion and it’s the easiest to implement.

Here is an example of traversing a Binary Tree implemented in Pseudo Code:

traversal(root)
  if root does not exist return null;

  left side traversal = traversal(root.left)
  right side traversal = traversal(root.right)

  return root;

Notice: Our base case is to return null if the root does not exist. This will not always be the exact base case. We traverse the left and right paths respectively then return root.

Here is an example of traversing a Binary Tree implemented in Javascript:

function traversal(root) {
  if (!root) return null;

  let left = traversal(root.left);
  let right = traversal(root.right);

  return root;
}

Sample Question:

function invertTree(root) {
  // Base case
  if (root === null) return null;

  // Traverse left and right paths
  let left = invertTree(root.left);
  let right = invertTree(root.right);

  // Invert the paths
  root.left = right;
  root.right = left;

  // Return
  return root;
}

Sample Question Link