Problem of the Day
A new programming or logic puzzle every Mon-Fri

Today's problem is a bit of a tough one depending on your programming background. The goal is to take in a binary tree and print out the nodes in level order (your choice on left to right or right to left). For instance the answer for

would be F, B, G, A, D, I, C, E, H (using left to right ordering).

Comments:

• PyBanana - 10 years, 3 months ago

  Python 2.7. I think this works.

  class Tree:
      def __init__(self, val):
          self.right = None
          self.left = None
          self.value = val
      def add(self, val):
          if self.value > val:
              if self.left:
                  self.left.add(val)
              else:
                  self.left = Tree(val)
          else:
              if self.right:
                  self.right.add(val)
              else:
                  self.right = Tree(val)
  
  def printTreeLevels(tree):
      depth = [tree]
      while len(depth) > 0:
          nxt = []
          for n in depth:
              print n.value, '->',
              if n.left:
                  nxt.append(n.left)
              if n.right:
                  nxt.append(n.right)
          depth = nxt
  

  reply permalink

• Max Burstein - 10 years, 3 months ago

  Your printTreeLevels does seem like it will work. Good job!

  reply permalink

• Anonymous - 10 years, 3 months ago

  I'm a day late... but i liked the task.. and well the solution is pretty small in haskell:

  data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Eq, Show)
  
  levelOrderTraversal :: (Eq a) => (Tree a) -> [a]
  levelOrderTraversal tree = createList [tree]
      where
          createList [] = []
          createList ((Empty):queue) = createList queue
          createList (h@(Node n l r):queue) = n : (createList (queue++[l]++[r]))
  

  reply permalink

• David - 10 years, 3 months ago

  The functional bits:

  typedef struct {
    char *array;
    size_t size;
  } Array;
  
  void initBinTree(Array *a, size_t initialSize) {
    a->array = (char *)malloc(initialSize * sizeof(char));
    a->size = initialSize;
    for(int i = 0; i < a->size; i++) {
      a->array[i] = 0;
    }
  }
  
  void treeAdd(Array *a, char element) {
    int curIndex = 1;
    while(a->array[curIndex-1] != 0) {
      if((int)a->array[curIndex-1] < (int)element) {
        curIndex *= 2;
      }
      else {
        if((int)a->array[curIndex-1] > (int)element) {
          curIndex = 2*curIndex + 1;
        }
        else{
          break;
        }
      }
      if(curIndex > a->size) {
        a->size *= 2;
        a->array = (char *)realloc(a->array, a->size * sizeof(char));
        for(int i = a->size/2; i < a->size; i++) {
          a->array[i] = 0;
        }
        break;
      }
    }
    a->array[curIndex-1] = element;
  }
  
  void freeTree(Array *a) {
    free(a->array);
    a->array = 0;
    a->size = 0;
  }
  
  void printTreeByLevel(Array* a) {
    for(int i = 0; i < a->size; i++) {
      if(a->array[i] != 0) {
        printf("%c", a->array[i]);
      }
    }
    printf("\n");
  }
  

  reply permalink