Tree Traversal | Level order


import java.util.Queue;
import java.util.LinkedList;

class LevelOrderTreeTraversal {
    private static Node root;
    
    void leverOrderUsingQueue(Node root) {
        if(root == null) {
            return;
        }
        Queue queue  = new LinkedList<>();
        queue.add(root);
        Node current;
        while(!queue.isEmpty()) {
            // dequeue from queue
            current = queue.poll();
            System.out.print(current.data + " ");
            
            // enqueue left node 
            if(current.left != null) {
                queue.add(current.left);
            }
            // enqueue right node 
            if(current.right != null) {
                queue.add(current.right);
            }
        }
    }
    
    /**
     * Time to print n levels is O(n^2)
     */ 
    void leverOrderUsingRecursion(Node root) {
        if(root == null) {
            return;
        }
        int height = height(root);
        for(int i = 0; i <= height; i++) {
            printLevel(root, i);
            System.out.println();
        }
    }
    
    /**
     * Time to print level is O(n)
     */ 
    void printLevel(Node root, int level) {
        // return if null 
        if(root == null) {
            return;
        }
        if(level == 0) {
            System.out.print(root.data + " ");
            return;
        } else if(level > 0) {
            printLevel(root.left, level - 1);
            printLevel(root.right, level - 1);
        }
        
    }
    
    Node populateTree() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        return root;
    }
    
    int height(Node root) {
        // height starts from 0 and lever starts from 1
        if(root == null) {
            return -1;
        }
        // calculate height of left and right sub trees
        int lHeight = height(root.left);
        int rHeight = height(root.right);
        
        // return larger height
        return (lHeight > rHeight ? lHeight : rHeight) + 1;
    }
    
	public static void main (String[] args) {
		LevelOrderTreeTraversal tree = new LevelOrderTreeTraversal();
		root = tree.populateTree();
        
        System.out.println("Lever order traversal using queue :");
        tree.leverOrderUsingQueue(root);
        
        System.out.println("\nLevel order traversal using recursion :");
        tree.leverOrderUsingRecursion(root);
        
        
        System.out.println("\nHeight of tree : " + tree.height(root));
	}
	private static class Node {
	    Node left;
	    int data;
	    Node right;
	    public Node(int data) {
	        this.data = data;
	    }
	}
}

Output
Lever order traversal using queue :
1 2 3 4 5 6 7 
Level order traversal using recursion :
1 
2 3 
4 5 6 7 

Height of tree : 2

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance