Alg.25 BST Traversal

From algoexpert.io

This one will uses 3 ways to traverse a BST (in-order/pre-order/post-order), the code implementation is pretty straightforward:

public static List<Integer> inOrderTraverse(BST tree, List<Integer> array) {
      BST current = tree;
      if (current != null) {
          inOrderTraverse(current.left, array);
          array.add(current.value);
          inOrderTraverse(current.right, array);
      }
  return array;
}

public static List<Integer> preOrderTraverse(BST tree, List<Integer> array) {
      BST current = tree;
      if (current != null) {
          array.add(current.value);
          preOrderTraverse(current.left, array);
          preOrderTraverse(current.right, array);
      }
  return array;
}

public static List<Integer> postOrderTraverse(BST tree, List<Integer> array) {
      BST current = tree;
      if (current != null) {
          postOrderTraverse(current.left, array);
          postOrderTraverse(current.right, array);
          array.add(current.value);
      }
  return array;
}

Time complexity: O(n); Space complexity: O(n).

Donate