Tuesday, October 6, 2015

Non-recursive level order traversal of a binary tree

Java Code:

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
   
    public TreeNode() {
       
    }
   
    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

//Non-recursive LevelOrder Traversal
    public String levelOrderTraversal(TreeNode node) {
        StringBuilder traversal = new StringBuilder();
        if(node == null) {
            return traversal.toString();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        int thisLevel = 1;
        int nextLevel = 0;
        while(!queue.isEmpty()) {
            for(int i=0; i<thisLevel; i++) {
                node = queue.remove();
                traversal.append(node.data);
                if(node.left != null && node.right != null) {
                    nextLevel += 2;
                    queue.add(node.left);
                    queue.add(node.right);
                }
                else if(node.left != null || node.right != null) {
                    nextLevel += 1;
                    if(node.left != null) {
                        queue.add(node.left);
                    }
                    else {
                        queue.add(node.right);
                    }
                }
            }
            thisLevel = nextLevel;
            nextLevel = 0;
        }
        return traversal.toString();
    }

Unit Tests:

public class TreeProgramsTest {

    TreeNode root;
    @Before
    public void initialize() {
        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
    }

    @Test
    public void testLevelOrderTraversal() {
        TreeTraversalPrograms treeTraversalPrograms = new TreeTraversalPrograms();
        Assert.assertTrue(treeTraversalPrograms.levelOrderTraversal(root).equals("123456"));
    }
}