BST Level Order Traversal

BST Construction is covered here.

Sample tree:

           5
        /     \
       2       9
    /     \      \
    1     3       10

Post Order traversal:

Each node level by level.

[
  [5],
  [2, 9],
  [1, 3, 10]
]

Recursive solution:

var levelOrder = function (root) {
  if (root == null) return []
  var out = []
  function help(level, out, node) {
    if (node == null) return
    if (out.length <= level) out.push([])
    out[level].push(node.val)
    help(level + 1, out, node.left)
    help(level + 1, out, node.right)
  }
  help(0, out, root)
  return out
}

Iterative solution:

Breadth first search, using a queue.

 var levelOrder1 = function(root) {
     if(root==null)return [];
     
     var out = [];
     var que = [root];
     
     while(que.length!=0){
         var len = que.length;
         var temp = [];
         
         for(var i=0; i<len; i++){
             var node = que.shift();
             temp.push(node.val);
             
             if(node.left)que.push(node.left);
             if(node.right)que.push(node.right);
         }
         out.push(temp);
     }
     
     return out;
 };

Other BST traversals:


Written by Gagandeep Rangi who likes to talk about himself in third person. Twitter Instagram