package algoexpert.medium;

import java.util.ArrayList;

/*

PROBLEM:

Traverse BST

- inorder

- preorder

- postorder

time : O(n) | space : O(n)

*/

public class BSTTraverse

{

static class BST {

public int value;

public BST left;

public BST right;

public BST(int value) {

this.value = value;

}

}

public static ArrayList<Integer> inOrderTraverse(BST tree, ArrayList<Integer> array) {

// LnR

if (tree != null)

{

inOrderTraverse(tree.left, array);

array.add(tree.value);

inOrderTraverse(tree.right, array);

}

return array;

}

public static ArrayList<Integer> preOrderTraverse(BST tree, ArrayList<Integer> array) {

// nLR

if (tree != null)

{

array.add(tree.value);

preOrderTraverse(tree.left, array);

preOrderTraverse(tree.right, array);

}

return array;

}

public static ArrayList<Integer> postOrderTraverse(BST tree, ArrayList<Integer> array) {

// LRn

if (tree != null)

{

postOrderTraverse(tree.left, array);

postOrderTraverse(tree.right, array);

array.add(tree.value);

}

return array;

}

}