Binary tree level order traversal

Question

Three types of tree traversals are inorder, preorder, and post order.

A fourth, less often used, traversal is level-order traversal. In a level-order traveresal, all nodes at depth "d" are processed before any node at depth d + 1. Level-order traversal differs from the other traversals in that it is not done recursively; a queue is used, instead of the implied stack of recursion.

My questions on above text snippet are

1. Why level order traversals are not done recursively?
2. How queue is used in level order traversal? Request clarification with Pseudo code will be helpful.

Thanks!

Answer 1

Level order traversal is actually a BFS, which is not recursive by nature. It uses Queue instead of Stack to hold the next vertices that should be opened. The reason for it is in this traversal, you want to open the nodes in a FIFO order, instead of a LIFO order, obtained by recursion

as I mentioned, the level order is actually a BFS, and its [BFS] pseudo code [taken from wikipedia] is:

1  procedure BFS(Graph,source):
2      create a queue Q
3      enqueue source onto Q
4      mark source
5      while Q is not empty:
6          dequeue an item from Q into v
7          for each edge e incident on v in Graph:
8              let w be the other end of e
9              if w is not marked:
10                 mark w
11                 enqueue w onto Q

(*) in a tree, marking the vertices is not needed, since you cannot get to the same node in 2 different paths.

Answer 2

void levelorder(Node *n)
{    queue < Node * >q;

     q.push(n);


     while(!q.empty())
     {
             Node *node = q.front();
             cout<<node->value;
             q.pop();
             if(node->left != NULL)
             q.push(node->left);
             if (node->right != NULL)
             q.push(node->right);

     }

}

Answer 3

Instead of a queue, I used a map to solve this. Take a look, if you are interested. As I do a postorder traversal, I maintain the depth at which each node is positioned and use this depth as the key in a map to collect values in the same level

class Solution { public: map<int, vector<int> > levelValues; void recursivePrint(TreeNode *root, int depth){ if(root == NULL) return; if(levelValues.count(root->val) == 0) levelValues.insert(make_pair(depth, vector<int>())); levelValues[depth].push_back(root->val); recursivePrint(root->left, depth+1); recursivePrint(root->right, depth+1); } vector<vector<int> > levelOrder(TreeNode *root) { recursivePrint(root, 1); vector<vector<int> > result; for(map<int,vector<int> >::iterator it = levelValues.begin(); it!= levelValues.end(); ++it){ result.push_back(it->second); } return result; } };

The entire solution can be found here - http://ideone.com/zFMGKU The solution returns a vector of vectors with each inner vector containing the elements in the tree in the correct order.

you can try solving it here - https://oj.leetcode.com/problems/binary-tree-level-order-traversal/

And, as you can see, we can also do this recursively in the same time and space complexity as the queue solution!

Answer 4

https://github.com/arun2pratap/data-structure/blob/master/src/main/java/com/ds/tree/binarytree/BinaryTree.java

for complete can look out for the above link.

 public void levelOrderTreeTraversal(List<Node<T>> nodes){
    if(nodes == null || nodes.isEmpty()){
        return;
    }
    List<Node<T>> levelNodes = new ArrayList<>();
    nodes.stream().forEach(node -> {
        if(node != null) {
            System.out.print(" " + node.value);
            levelNodes.add(node.left);
            levelNodes.add(node.right);
        }
    });
    System.out.println("");
    levelOrderTreeTraversal(levelNodes);
}

Also can check out http://www.geeksforgeeks.org/

here you will find Almost all Data Structure related answers.

Answer 5

Level order traversal implemented by queue

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def levelOrder(root: TreeNode) -> List[List[int]]:
    res = []    # store the node value

    queue = [root]
    while queue:
        node = queue.pop()
        
        # visit the node
        res.append(node.val)
        
        if node.left:
            queue.insert(0, node.left)
        if node.right:
            queue.insert(0, node.right)
            
    return res

Recursive implementation is also possible. However, it needs to know the max depth of the root in advance.

def levelOrder(root: TreeNode) -> List[int]:
    res = []
    max_depth = maxDepth(root)
    for i in range(max_depth):
        # level start from 0 to max_depth-1
        visitLevel(root, i, action)
    return res

def visitLevel(root:TreeNode, level:int, res: List):
    if not root:
        return 
    if level==0:
        res.append(node.val)
    else:
        self.visitLevel(root.left, level-1, res)
        self.visitLevel(root.right, level-1, res)
            

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return max([ maxDepth(root.left), maxDepth(root.right)]) + 1

Answer 6

My questions on above text snippet are

1. Why level order traversals are not done recursively?
2. How queue is used in level order traversal? Request clarification with Pseudo code will be helpful.

I think it'd actually be easier to start with the second question. Once you understand the answer to the second question, you'll be better prepared to understand the answer to the first.

How level order traversal works

I think the best way to understand how level order traversal works is to go through the execution step by step, so let's do that.

We have a tree.

We want to traverse it level by level.

So, the order that we'd visit the nodes would be A B C D E F G.

To do this, we use a queue. Remember, queues are first in, first out (FIFO). I like to imagine that the nodes are waiting in line to be processed by an attendant.

Let's start by putting the first node A into the queue.

Ok. Buckle up. The setup is over. We're about to start diving in.

The first step is to take A out of the queue so it can be processed. But wait! Before we do so, let's put A's children, B and C, into the queue also.

Note: A isn't actually in the queue anymore at this point. I grayed it out to try to communicate this. If I removed it completely from the diagram, it'd make it harder to visualize what's happening later on in the story.

Note: A is being processed by the attendant at the desk in the diagram. In real life, processing a node can mean a lot of things. Using it to compute a sum, send an SMS, log to the console, etc, etc. Going off the metaphor in my diagram, you can tell the attendant how you want them to process the node.

Now we move on to the node that is next in line. In this case, B.

We do the same thing that we did with A: 1) add the children to the line, and 2) process the node.

Hey, check it out! It looks like what we're doing here is going to get us that level order traversal that we were looking for! Let's prove this to ourselves by continuing the step through.

Once we finish with B, C is next in line. We place C's children at the back of the line, and then process C.

Now let's see what happens next. D is next in line. D doesn't have any children, so we don't place anything at the back of the line. We just process D.

And then it's the same thing for E, F, and G.

Why it's not done recursively

Imagine what would happen if we used a stack instead of a queue. Let's rewind to the point where we had just visited A.

Here's how it'd look if we were using a stack.

Now, instead of going "in order", this new attendant likes to serve the most recent clients first, not the ones who have been waiting the longest. So C is who is up next, not B.

Here's where the key point is. Where the stack starts to cause a different processing order than we had with the queue.

Like before, we add C's children and then process C. We're just adding them to a stack instead of a queue this time.

Now, what's next? This new attendant likes to serve the most recent clients first (ie. we're using a stack), so G is up next.

I'll stop the execution here. The point is that something as simple as replacing the queue with a stack actually gives us a totally different execution order. I'd encourage you to finish the step through though.

You might be thinking: "Ok... but the question asked about recursion. What does this have to do with recursion?" Well, when you use recursion, something sneaky is going on. You never did anything with a stack data structure like s = new Stack(). However, the runtime uses the call stack. This ends up being conceptually similar to what I did above, and thus doesn't give us that A B C D E F G ordering we were looking for from level order traversal.

Answer 7

For your point 1) we can use Java below code for level order traversal in recursive order, we have not used any library function for tree, all are user defined tree and tree specific functions -

class Node
{
    int data;
    Node left, right;
    public Node(int item)
    {
        data = item;
        left = right = null;
    }

    boolean isLeaf() { return left == null ? right == null : false; }
}

public class BinaryTree {
    Node root;

    Queue<Node> nodeQueue = new ConcurrentLinkedDeque<>();

    public BinaryTree() {
        root = null;
    }

    public static void main(String args[]) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.right.left.left = new Node(8);
        tree.root.right.left.right = new Node(9);
        tree.printLevelOrder();
    }

    /*Level order traversal*/
    void printLevelOrder() {
        int h = height(root);
        int i;
        for (i = 1; i <= h; i++)
            printGivenLevel(root, i);
        System.out.println("\n");
    }

    void printGivenLevel(Node root, int level) {
        if (root == null)
            return;
        if (level == 1)
            System.out.print(root.data + " ");

        else if (level > 1) {
            printGivenLevel(root.left, level - 1);
            printGivenLevel(root.right, level - 1);
        }
    }

    /*Height of Binary tree*/
    int height(Node root) {
        if (root == null)
            return 0;
        else {
            int lHeight = height(root.left);
            int rHeight = height(root.right);

            if (lHeight > rHeight)
                return (lHeight + 1);
            else return (rHeight + 1);
        }
    }
} 

For your point 2) If you want to use non recursive function then you can use queue as below function-

public void levelOrder_traversal_nrec(Node node){
        System.out.println("Level order traversal !!! ");
        if(node == null){
            System.out.println("Tree is empty");
            return;
        }
         nodeQueue.add(node);
        while (!nodeQueue.isEmpty()){
            node = nodeQueue.remove();
            System.out.printf("%s ",node.data);
            if(node.left !=null)
                nodeQueue.add(node.left);
            if (node.right !=null)
                nodeQueue.add(node.right);
        }
        System.out.println("\n");
    }