HelloKoding

Practical coding guides

Depth First Traversal in Tree

In this article, you will learn about the depth-first traversal operation in a Tree data structure

Tree traversal is a process of visiting each node in a tree exactly once. Unlike linear data structures such as array and linked list which is canonically traversed in linear order, a tree may be traversed in depth-first or breadth-first order

Depth-First Traversal

There are 3 ways of depth-first traversal, typically, classified by the orders in which nodes are visited

  • Pre-order visits the parent node before all traversal to the left and the right subtree
  • In-order visits the parent node between traversal to the left and the right subtree
  • Post-order visits the parent node after all traversal to the left and the right subtree

Example

a Binary Search Tree

Depth-first traversal orders for the above tree

  • Pre-oder is 7-2-1-3-9
  • In-order is 1-2-3-7-9
  • Post-oder is 1-3-2-9-7

Implementation with Recursive algorithm

TreeDepthFirstTraversalRecursively.java

package com.hellokoding.algorithm;

import com.hellokoding.datastructure.BSTByLinkedList;

public class TreeDepthFirstTraversalRecursively extends BSTByLinkedList {
    public void preTraversal(Node node) {
        if (node == null) return;

        System.out.println(node);
        preTraversal(node.left);
        preTraversal(node.right);
    }

    public void inTraversal(Node node) {
        if (node == null) return;

        inTraversal(node.left);
        System.out.println(node);
        inTraversal(node.right);
    }

    public void postTraversal(Node node) {
        if (node == null) return;

        postTraversal(node.left);
        postTraversal(node.right);
        System.out.println(node);
    }

    public static void main(String[] args) {
        TreeDepthFirstTraversalRecursively tree = new TreeDepthFirstTraversalRecursively();
        tree.insert(7);
        tree.insert(2);
        tree.insert(3);
        tree.insert(1);
        tree.insert(9);

        System.out.println("Pre-order Traversal");
        tree.preTraversal(tree.root);
        System.out.println();

        System.out.println("In-order Traversal");
        tree.inTraversal(tree.root);
        System.out.println();

        System.out.println("Post-order Traversal");
        tree.postTraversal(tree.root);
    }
}

Implementation with Iterative algorithm

TreeDepthFirstTraversalIterably.java

package com.hellokoding.algorithm;

import com.hellokoding.datastructure.BSTByLinkedList;

import java.util.ArrayDeque;
import java.util.Deque;

public class TreeDepthFirstTraversalIterably extends BSTByLinkedList {
    public void preTraversal(Node node) {
        if (node == null) return;

        Deque<Node> stack = new ArrayDeque<>();
        stack.push(node);

        while (!stack.isEmpty()) {
            Node currentNode = stack.pop();
            System.out.println(currentNode);

            if (currentNode.right != null)
                stack.push(currentNode.right);

            if (currentNode.left != null)
                stack.push(currentNode.left);
        }
    }

    public void inTraversal(Node node) {
        Deque<Node> stack = new ArrayDeque<>();

        while (node != null) {
            stack.push(node);
            node = node.left;
        }

        while (!stack.isEmpty()) {
            node = stack.pop();
            System.out.println(node);

            if (node.right != null)
                stack.push(node.right);
        }
    }

    public void postTraversal(Node node) {
        Deque<Node> stack = new ArrayDeque<>();

        while (node != null) {
            stack.push(node);
            node = node.left;
        }

        Node lastVisitedNode = null;
        while (!stack.isEmpty()) {
            node = stack.peek();

            if (node.right != null && node.right != lastVisitedNode) {
                stack.push(node.right);
            } else {
                System.out.println(node);
                lastVisitedNode = stack.pop();
            }
        }
    }

    public static void main(String[] args) {
        TreeDepthFirstTraversalIterably tree = new TreeDepthFirstTraversalIterably();
        tree.insert(7);
        tree.insert(2);
        tree.insert(3);
        tree.insert(1);
        tree.insert(9);

        System.out.println("Pre-order Traversal");
        tree.preTraversal(tree.root);
        System.out.println();

        System.out.println("In-order Traversal");
        tree.inTraversal(tree.root);
        System.out.println();

        System.out.println("Post-order Traversal");
        tree.postTraversal(tree.root);
    }
}

BSTByLinkedList is defined in Binary Search Tree Data Structure

Follow HelloKoding