Tree data structure part 5/5: extracting useful information from tree using recursion: PreOrder, InOrder, PostOrder and more

*Prerequisite: Tree data structure part 4/5: understanding function call stack and recursion.

This tutorial is a part of the Data Structures and Algorithms class:

• Extracting useful information from tree with recursion
• PreOrder traversal
• InOrder traversal
• PostOrder traversal
• PreOrder, InOrder, PostOrder traversal summary
• How fast to insert/delete/access/search data
• Algorithms: how to extract useful information out of input

Extracting useful information from tree with recursion

At this point, you should have a pretty good understanding how function call stack and recursion works. We will now apply this knowledge to extract useful information from tree by using recursion. Reminder:

Traverse means walk, tree traversal means walking the tree. Tree traversal is just a fancy name for tree node visitation in a particular order. With recursion, we have 3 popular, official traversal names: PreOrder, InOrder and PostOrder traversal.

PreOrder traversal

Usefulness of this order of node visitation: whenever it gives value to your application.

// Binary Search Tree, without self-balancing
class BinarySearchTree {

  // ...
  // preorder traversal
  preOrder() {
    if (this.root == null) {
      return null
    } else {
      var result = []
      traversePreOrder(this.root)
      return result

      function traversePreOrder(node) {
        result.push(node.data)
        node.left && traversePreOrder(node.left)
        node.right && traversePreOrder(node.right)
      }
    }
  }
  // ...
}

$ node binary-search-tree-data-structure.js
preOrder(): [ 6, 4, 1, 5, 8, 10 ]

InOrder traversal

Usefulness of this order of node visitation: BST print min -> max and whenever it gives value to your application.

// Binary Search Tree, without self-balancing
class BinarySearchTree {

  // ...
  // inorder traversal (print min -> max)
  inOrder() {
    if (this.root == null) {
      return null
    } else {
      var result = []
      traverseInOrder(this.root)
      return result

      function traverseInOrder(node) {
        node.left && traverseInOrder(node.left)
        result.push(node.data)
        node.right && traverseInOrder(node.right)
      }
    }
  }
  // ...
}

$ node binary-search-tree-data-structure.js
inOrder(): [ 1, 4, 5, 6, 8, 10 ]

PostOrder traversal

Usefulness of this order of node visitation: whenever it gives value to your application.

// Binary Search Tree, without self-balancing
class BinarySearchTree {

  // ...
  // postorder traversal
  postOrder() {
    if (this.root == null) {
      return null
    } else {
      var result = []
      traversePostOrder(this.root)
      return result

      function traversePostOrder(node) {
        node.left && traversePostOrder(node.left)
        node.right && traversePostOrder(node.right)
        result.push(node.data)
      }
    }
  }
}

$ node binary-search-tree-data-structure.js
postOrder(): [ 1, 5, 4, 10, 8, 6 ]

PreOrder, InOrder, PostOrder traversal summary

3 lines of code, we have total 6 possible arrangements. 3 of them has offical names. The rest 3 doesn't. But they actually have the same usefulness. For simplicity, we can call them: prereversedorder, inreversedorder and postreversedorder. Discover them yourself!

How fast to insert/delete/access/search data

⬆️ Time complexity (worst case) per operation

Algorithms: how to extract useful information out of input

Real life interview questions

1. Draw call stack + recursion tree for PreOrder traversal.
2. Draw call stack + recursion tree for InOrder traversal.
3. Draw call stack + recursion tree for PostOrder traversal.
4. Randomly choose one of: PreReversedOrder, InReversedOrder and PostReversedOrder traversal, draw call stack + recursion tree for it.
5. Solve problem 3, 4 in popular tree problems.
6. Solve Leetcode #99: Recover Binary Search Tree
7. Solve Leetcode #124: Binary Tree Maximum Path Sum
8. Solve Leetcode #515: Find Largest Value in Each Tree Row