# HelloKoding

Practical coding guides

# Depth First Traversal in Tree

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

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;

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 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