Blog Details

Tree Traversal code implementation in Recursive and Iterative Ways

1. Description

Recursive way is based on computer program, the function calling stack. While iterative way is programmer use stack to simulate it.

2. Solution

#TreeNode.java
package com.frank.common;

public class TreeNode {
	public int val;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int v) {
		this.val = v;
	}
}
#TreeTraversal.java
package com.frank.tree.traversal;


import java.util.Stack;

import com.frank.common.TreeNode;

public class TreeTraversal {
	// Recursive Traversal
	/**
	 * PreOrder Traversal
	 */
	public void preOrder(TreeNode root) {
		if(root == null) return;
		System.out.print(root.val + " ");
		preOrder(root.left);
		preOrder(root.right);
	}
	
	/**
	 * InOrder Traversal
	 * 
	 * - If the tree is BST, the printing order is ascending.
	 * 
	 */
	public void inOrder(TreeNode root) {
		if(root == null) return;
		inOrder(root.left);
		System.out.print(root.val + " ");
		inOrder(root.right);
	}
	
	/**
	 * PostOrder Traversal
	 *  
	 *  - root is in the last element
	 */
	public void postOrder(TreeNode root) {
		if(root == null) return;
		postOrder(root.left);
		postOrder(root.right);
		System.out.print(root.val + " ");
	}
	
	// Iterative traversal 
	public void preOrderIterative(TreeNode root) {
		TreeNode cur = root;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while(cur != null) {
			System.out.print(cur.val + " ");
			stack.push(cur);
			cur = cur.left;
		}
		
		while(!stack.isEmpty()) {
			TreeNode p = stack.pop();
			p = p.right;
			while(p != null) {
				System.out.print(p.val + " ");
				stack.push(p);
				p = p.left;
			}
		}
	}
	
	/**
	 * inOrder Iterative 
	 * 
	 */
	public void inOrderIterative(TreeNode root) {
		TreeNode cur = root;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while(cur != null) {
			stack.push(cur);
			cur = cur.left;
		}
		while(!stack.isEmpty()) {
			TreeNode p = stack.pop();
			System.out.print(p.val + " ");
			p = p.right;
			while(p != null) {
				stack.push(p);
				p = p.left;
			}
		}
	}
	
	/**
	 * Post oder Iterative
	 * 
	 */
	public void postOrderIterative(TreeNode root) {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		Stack<Integer> out = new Stack<Integer>();
		stack.push(root);
		while(!stack.isEmpty()) {
			TreeNode cur = stack.pop();
			out.push(cur.val);
			if(cur.left != null) {
				stack.push(cur.left);
			}
			
			if(cur.right != null) {
				stack.push(cur.right);
			}
		}
		
		while(!out.isEmpty()) {
			System.out.print(out.pop() + " ");
		}
	}
}
#Test Cases
package junit.test;

import org.junit.jupiter.api.Test;

import com.frank.common.TreeNode;
import com.frank.tree.traversal.TreeTraversal;

public class TreeTraversalTest {
	@Test
	public void testPreOrder() {
		TreeTraversal traversal = new TreeTraversal();
		TreeNode root = new TreeNode(10);
		TreeNode node5 = new TreeNode(5);
		TreeNode node18 = new TreeNode(18);
		TreeNode node3 = new TreeNode(3);
		TreeNode node7 = new TreeNode(7);
		TreeNode node12 = new TreeNode(12);
		TreeNode node21 = new TreeNode(21);
		root.left = node5;
		root.right = node18;
		node5.left = node3;
		node5.right = node7;
		node18.left = node12;
		node18.right = node21;
		traversal.preOrder(root);
	}
	
	@Test
	public void testInOrder() {
		TreeTraversal traversal = new TreeTraversal();
		TreeNode root = new TreeNode(10);
		TreeNode node5 = new TreeNode(5);
		TreeNode node18 = new TreeNode(18);
		TreeNode node3 = new TreeNode(3);
		TreeNode node7 = new TreeNode(7);
		TreeNode node12 = new TreeNode(12);
		TreeNode node21 = new TreeNode(21);
		root.left = node5;
		root.right = node18;
		node5.left = node3;
		node5.right = node7;
		node18.left = node12;
		node18.right = node21;
		traversal.inOrder(root);
	}
	
	@Test
	public void testPostOrder() {
		TreeTraversal traversal = new TreeTraversal();
		TreeNode root = new TreeNode(10);
		TreeNode node5 = new TreeNode(5);
		TreeNode node18 = new TreeNode(18);
		TreeNode node3 = new TreeNode(3);
		TreeNode node7 = new TreeNode(7);
		TreeNode node12 = new TreeNode(12);
		TreeNode node21 = new TreeNode(21);
		root.left = node5;
		root.right = node18;
		node5.left = node3;
		node5.right = node7;
		node18.left = node12;
		node18.right = node21;
		traversal.postOrder(root);
	}

	@Test
	public void testPreOrderIteractive() {
		TreeTraversal traversal = new TreeTraversal();
		TreeNode root = new TreeNode(10);
		TreeNode node5 = new TreeNode(5);
		TreeNode node18 = new TreeNode(18);
		TreeNode node3 = new TreeNode(3);
		TreeNode node7 = new TreeNode(7);
		TreeNode node12 = new TreeNode(12);
		TreeNode node21 = new TreeNode(21);
		root.left = node5;
		root.right = node18;
		node5.left = node3;
		node5.right = node7;
		node18.left = node12;
		node18.right = node21;
		traversal.preOrderIterative(root);
	}
	
	@Test
	public void testInOrderIterative() {
		TreeTraversal traversal = new TreeTraversal();
		TreeNode root = new TreeNode(10);
		TreeNode node5 = new TreeNode(5);
		TreeNode node18 = new TreeNode(18);
		TreeNode node3 = new TreeNode(3);
		TreeNode node7 = new TreeNode(7);
		TreeNode node12 = new TreeNode(12);
		TreeNode node21 = new TreeNode(21);
		root.left = node5;
		root.right = node18;
		node5.left = node3;
		node5.right = node7;
		node18.left = node12;
		node18.right = node21;
		traversal.inOrderIterative(root);
	}
	
	@Test
	public void testPostOrderIterative() {
		TreeTraversal traversal = new TreeTraversal();
		TreeNode root = new TreeNode(10);
		TreeNode node5 = new TreeNode(5);
		TreeNode node18 = new TreeNode(18);
		TreeNode node3 = new TreeNode(3);
		TreeNode node7 = new TreeNode(7);
		TreeNode node12 = new TreeNode(12);
		TreeNode node21 = new TreeNode(21);
		root.left = node5;
		root.right = node18;
		node5.left = node3;
		node5.right = node7;
		node18.left = node12;
		node18.right = node21;
		traversal.postOrderIterative(root);
	}
}