Coding For Interviews -- This week's question: Level Order Tree Print This week's question is to print a binary tree of integers in level order. Level-order printing means printing each row of the tree from left to right, from root row to the deepest row. After each row, print a newline. Bonus: Can you make one version that supports binary trees…

gistfile1.txt

package cfi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * This week's question is to print a binary tree of integers in level order.
 *
 * Level-order printing means printing each row of the tree from left to right, from root row to the deepest row. 
 * After each row, print a newline.
 *
 * Bonus: Can you make one version that supports binary trees, and another that can handle any K-ary tree?
 *
 * @author Bernie Margolis
 */
public class LevelOrderTreeTraversal {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println("Binary tree output:");
		List<TreeNode> exampleRoot = Arrays.asList(new TreeNode[] { setupBinaryTest() });
		printNodes(exampleRoot);

		System.out.println("K-ary tree output:");
		exampleRoot = Arrays.asList(new TreeNode[] { setupArbitraryTest() });
		printNodes(exampleRoot);
	}
	
	/**
	 * This method prints recursively prints trees of integers in level-order
	 * @param nodesInRow The TreeNodes for the current level to be printed
	 */
	private static void printNodes(List<TreeNode> nodesInRow) {
		List<Integer> valuesInLevel = new ArrayList<Integer>();
		List<TreeNode> nodesInNextLevel = new ArrayList<TreeNode>();
		if (nodesInRow != null && !nodesInRow.isEmpty()) {
			// Compile a list of all values in the current row as
			// well as a list of nodes that will be in the next row
			for (TreeNode node : nodesInRow) {
				if (node != null) {
					valuesInLevel.add(node.getValue());
					nodesInNextLevel.addAll(node.getChildren());					
				}
			}
			
			StringBuilder valuesString = new StringBuilder();
			for (int value : valuesInLevel) {
				valuesString.append(value).append(" ");
			}
			System.out.println(valuesString.toString());
		}
		
		if (!nodesInNextLevel.isEmpty()) {
			printNodes(nodesInNextLevel);
		}
	}
	
	/**
	 * This interface is implemented by classes used to represent an integer node in a k-ary tree
	 */
	interface TreeNode {
		/**
		 * @return this node's value
		 */
		int getValue();
		
		/**
		 * @return List of the node's children ordered from left to right
		 */
		List<TreeNode> getChildren();
	}
	
	/**
	 * This class represents a node in a binary tree of integer values
	 */
	static class BinaryTreeNode implements TreeNode {
		private int value;
		private BinaryTreeNode leftChild;
		private BinaryTreeNode rightChild;
		
		/**
		 * Construct a node containing the specified value
		 * @param value this node's integer value
		 */
		BinaryTreeNode(int value) {
			this.value = value;
			this.leftChild = null;
			this.rightChild = null;
		}
		
		/**
		 * Set this node's left child to the specified BinaryTreeNode
		 * @param leftChild BinaryTreeNode representing the left child
		 */
		public void setLeftChild(BinaryTreeNode leftChild) {
			this.leftChild = leftChild;
		}
			
		/**
		 * Set this node's right child to the specified BinaryTreeNode
		 * @param rightChild BinaryTreeNode representing the right child
		 */
		public void setRightChild(BinaryTreeNode rightChild) {
			this.rightChild = rightChild;
		}
		
		/**
		 * @return List of the node's children ordered from left to right.
		 */
		public List<TreeNode> getChildren() {
			List<TreeNode> children = new ArrayList<TreeNode>();
			if (leftChild != null) {
				children.add(leftChild);
			}
			if (leftChild != null) {
				children.add(rightChild);
			}
			return children;
		}
		
		
		public int getValue() {
			return this.value;
		}
	}
	
	/**
	 * This class represents a node in a k-ary tree of integer values
	 */
	static class ArbitraryTreeNode implements TreeNode {
		private int value;
		private List<TreeNode> children;
		
		/**
		 * Construct a node containing the specified value
		 * @param value this node's integer value
		 */
		ArbitraryTreeNode(int value) {
			this.value = value;
			this.children = new ArrayList<TreeNode>();
		}
		
		/**
		 * Set this node's nth child to the specified BinaryTreeNode.
		 * @param n position into which to insert the child.
		 * @param child ArbitraryTreeNode to place in this position.  
		 *              Note that null is an acceptable option here.
		 * @throws IllegalArgumentException when n is less than 0 or 
		 *         when n is greater than the number of existing children
		 */
		public void replaceNthChild(int n, ArbitraryTreeNode child) {
			if (n <= 0 || n >= this.children.size()) {
				throw new IllegalArgumentException("There is nothing to replace in position " + n);
			} else {
				this.children.remove(n);
				this.children.add(n, child);
			}
		}
		
		/**
		 * Add a child to this node's right-most position
		 * @param child TreeNode to add
		 */
		public void addChild(TreeNode child) {
			this.children.add(child);
		}
					
		/**
		 * @return List of the node's children ordered from left to right.
		 */
		public List<TreeNode> getChildren() {
			return Collections.unmodifiableList(children);
		}
		
		
		public int getValue() {
			return this.value;
		}
	}

	
	private static TreeNode setupBinaryTest() {
		// Build this tree:
		//        3
		//      /   \
		//     9    20
		//         /  \
		//        15   7
		
		BinaryTreeNode root = new BinaryTreeNode(3);
		BinaryTreeNode left = new BinaryTreeNode(9);
		BinaryTreeNode right = new BinaryTreeNode(20);
		right.setLeftChild(new BinaryTreeNode(15));
		right.setRightChild(new BinaryTreeNode(7));
		root.setLeftChild(left);
		root.setRightChild(right);
		
		// Test output should be:
		// 3
		// 9 20
		// 15 7
		return root;
	}
	
	private static TreeNode setupArbitraryTest() {
		// Build this tree:
		//        8
		//      / | \
		//     6  7  5
		//   / |     |
		//  3  0     9
		//         / | \
		//        42 76 54

		ArbitraryTreeNode eight = new ArbitraryTreeNode(8);
		ArbitraryTreeNode six = new ArbitraryTreeNode(6);
		ArbitraryTreeNode seven = new ArbitraryTreeNode(7);
		ArbitraryTreeNode five = new ArbitraryTreeNode(5);
		ArbitraryTreeNode three = new ArbitraryTreeNode(3);
		ArbitraryTreeNode o = new ArbitraryTreeNode(0);
		ArbitraryTreeNode nine = new ArbitraryTreeNode(9);
		ArbitraryTreeNode fourtyTwo = new ArbitraryTreeNode(42);
		ArbitraryTreeNode seventySix = new ArbitraryTreeNode(76);
		ArbitraryTreeNode fiftyFour = new ArbitraryTreeNode(54);
				
		eight.addChild(six);
		eight.addChild(seven);
		eight.addChild(five);

		six.addChild(three);
		six.addChild(o);

		five.addChild(nine);
		
		nine.addChild(fourtyTwo);
		nine.addChild(seventySix);
		nine.addChild(fiftyFour);

		// Test output should be:
		// 8
		// 6 7 5
		// 3 0 9
		// 42 76 54
		return eight;
	}
}