Recording 24: Traversals of BST

Given the drawing of a tree, print the node values for preorder, inorder, and postorder traversal of the tree.

• Preorder

  • Root → left → Right

    • A B D E C F

• Inorder 

  • Left → Root → Right

    • D B E A C F

• Postorder

  • Left → Right → Root

    • D E B F C A

Preorder method code

void preorder(TreeNode root) {

    if (root == null) return;

    System.out.print(root.val + " ");

    preorder(root.left);

    preorder(root.right);

}

Inorder method code

void inorder(TreeNode root) {

    if (root == null) return;

    inorder(root.left);

    System.out.print(root.val + " ");

    inorder(root.right);

}

Postorder method code

void postorder(TreeNode root) {

    if (root == null) return;

    postorder(root.left);

    postorder(root.right);

    System.out.print(root.val + " ");

}

What is Depth First Search (DFS)?

Exactly like preorder traversal (last-in/first-out)

What is Breadth First Search (BFS) ?

Similar to Queue (first-in/first-out) you go by level by level

Ex —> A, B, C, D , E, F

BFS Code

public void BFS () {

if (root == null) return;

Queue<TreeNode<E>> queue = new LinkedList<>();

queue.add(root);

while (!queue.isEmpty()) {

TreeNode<E> current = queue.poll();

System.out.print(current.getData() + " ");

if (current.getLeft() != null) queue.add(current.getLeft());

if (current.getRight() != null) queue.add(current.getRight());

        }

System.out.println();

}

DFS code

public void DFS() {

if (root == null) return;

        Deque<TreeNode<E>> stack = new ArrayDeque<>();

        stack.push(root);

        while (!stack.isEmpty()) {

            TreeNode<E> current = stack.pop();

            System.out.print(current.getData() + " ");

            if (current.getRight() != null) stack.push(current.getRight());

            if (current.getLeft() != null) stack.push(current.getLeft());

        }

        System.out.println();

    }